C++で桁の合計が4で割り切れる「A以上の最小の数」を見つけるプログラム

ある整数 A が与えられたとき、「A 以上で最も近い興味深い数（interesting number）」を求めることを考えましょう。ここで興味深い数とは、各桁の数字の合計が 4 で割り切れる数として定義されます。

たとえば、入力が A = 432 のとき、出力は 435 になります。これは 4 + 3 + 5 = 12 となり、12 が 4 で割り切れるためです。

解法の考え方

この問題はとてもシンプルな戦略で解決できます。A の各桁の合計が 4 で割り切れるようになるまで、A を 1 ずつ増やしていけばよいのです。

手順を疑似コードで表すと、次のようになります。

while ((A / 1000 + A mod 1000 / 100 + A mod 100 / 10 + A mod 10) mod 4) ≠ 0 の間:
    A を 1 増やす
A を返す

式中の各式は、次のようにして A から各桁の数字を取り出しています。

• A / 1000 … 千の位の数字
• A % 1000 / 100 … 百の位の数字
• A % 100 / 10 … 十の位の数字
• A % 10 … 一の位の数字

C++ による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int A) {
    while ((A / 1000 + A % 1000 / 100 + A % 100 / 10 + A % 10) % 4 != 0) {
        A++;
    }
    return A;
}

int main() {
    int A = 432;
    cout << solve(A) << endl;
}

入力

432

出力

435

注意点：この実装が正しく動くのは 4 桁まで

上記の solve() 関数は、千・百・十・一の位を直接取り出す方式のため、A が 9999 以下の 4 桁の数である場合にのみ正しく機能します。それ以上の桁数を扱いたい場合は、次のような digitSum() 関数を用意するのがおすすめです。

int digitSum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10; // 一の位を加算
        n /= 10;       // 一の位を切り捨てる
    }
    return sum;
}

この関数を使えば、任意の桁数の整数に対して桁の合計を求められます。判定部分を while (digitSum(A) % 4 != 0) A++; のように書き換えるだけで、より汎用的な実装になります。

計算量

1 回の桁合計の判定は O(1) で行えます。さらに、桁の合計が 4 の倍数になる数はごく近い距離に必ず現れるため、ループが回る回数はごくわずかです。その結果、このアルゴリズム全体は実質的に定数時間 O(1) で動作する、非常に効率的な解法と言えます。