C++で桁の合計がnとなる最小のラッキーナンバー(4と7のみで構成)を求める方法

問題の概要

ラッキーナンバーとは、10進表記がラッキーな数字である「4」と「7」のみで構成される正の整数のことです。この問題では、各桁の数字の合計がnと等しくなるような、最小のラッキーナンバーを求めます。

例

sum = 22 の場合、4 + 4 + 7 + 7 = 22 が成立するため、答えは 4477 となります。

アルゴリズム

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

処理の流れの解説

sum = 22 の場合、プログラムは次のように動作します。

1. 22は7で割り切れないため、4を引いて18にします(4のカウント:1)。
2. 18も7で割り切れないため、さらに4を引いて14にします(4のカウント:2)。
3. 14は7の倍数なので、7を引いて7にします(7のカウント:1)。
4. 残りの7を引いて0にします(7のカウント:2)。

結果として、4が2個・7が2個となり、「4」を先頭に並べた 4477 が出力されます。なお、sumが4と7の組み合わせで表せない場合(たとえば6など)は、sumが負になった時点で -1 を出力して終了します。