ตัวเลขต่ำสุดที่มีหลักเป็น 4 และ 7 เท่านั้น และผลรวมหลักเท่ากับค่าที่กำหนดใน C++

ข้อกำหนดโจทย์

Lucky numbers คือจำนวนเต็มบวกที่ตัวเลขในฐานสิบประกอบด้วยหลัก 4 และ 7 เท่านั้น งานคือหา lucky number ต่ำสุดที่มีผลรวมหลักเท่ากับ n

ตัวอย่าง

ถ้า sum = 22 lucky number คือ 4477 เพราะ 4 + 4 + 7 + 7 = 22

อัลกอริทึม

1. ถ้า sum เป็นจำนวนคูณของ 4 ผลลัพธ์จะมีแต่ 4
2. ถ้า sum เป็นจำนวนคูณของ 7 ผลลัพธ์จะมีแต่ 7
3. ถ้า sum ไม่ใช่จำนวนคูณของ 4 หรือ 7 เราสามารถลบหนึ่งในสองจำนวนนี้จนกว่า sum จะกลายเป็นจำนวนคูณของอีกตัว

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
void luckyNumber(int sum) {
  int a, b;
  a = b = 0;
  while (sum > 0) {
    if (sum % 7 == 0) {
      ++b;
      sum = sum - 7;
    } else if (sum % 4 == 0) {
      ++a;
      sum = sum - 4;
    } else {
      ++a;
      sum = sum - 4;
    }
  }
  cout << "Answer = ";
  if (sum < 0) {
    cout << "-1\n" << endl;
    return;
  }
  for (int i = 0; i < a; ++i) {
    cout << "4";
  }
  for (int i = 0; i < b; ++i) {
    cout << "7";
  }
  cout << endl;
}
int main() {
  int sum = 22;
  luckyNumber(sum);
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Answer = 4477