C++で数値dの倍数を加算した後に可能な最小の桁和を求める方法

この問題では、2つの整数 n と d が与えられ、n に d の倍数を加算したときに実現できる最小の桁和を求めることが課題となります。

問題の説明

n に対して d の k 倍（k = 1, 2, 3, …）を加算して得られる数値のうち、桁和が最も小さくなるものを見つけます。ここで扱う「桁和」は、各桁の合計が1桁になるまで計算を繰り返すデジタルルートに相当します。

入力例

n = 5230, d = 54

出力例

1

解説

5230 + (2 × 54) = 5338
5 + 3 + 3 + 8 = 19 → 1 + 9 = 10 → 1 + 0 = 1

解法のアプローチ

シンプルな解法としては、d の倍数を 1 倍から 8 倍まで順に試す方法があります。9 倍目以降は桁和が循環するため、それ以上調べる必要がないからです。これは法 9（mod 9）の性質に基づいています。ある数 a に対しては、次の関係が常に成り立ちます。

(a + d × (9k + l)) mod 9 = (a + d × l) mod 9

したがって、l を 1〜8 の範囲で変化させた場合の桁和だけを確認すれば十分であり、その中で最小の値を答えとして返します。

さらに、桁和は決して 1 より小さくなり得ないという事実も活用できます。計算の途中で桁和が 1 になった時点で即座に処理を打ち切ることで、無駄な計算を省くことができます。

実装例

#include <iostream>
using namespace std;
int calcDigitSum(int n) {
    int i = n % 9;
    if (i == 0)
        return 9;
    else
        return i;
}
int findMinDigitSum(int n, int d) {
    int minSum = 10;
    int number;
    for (int i = 1; i < 9; i++) {
        number = (n + i * d);
        minSum = min(minSum, calcDigitSum(number));
        if(minSum == 1)
            return minSum;
    }
    return minSum;
}
int main() {
    int n = 5230, d = 54;
    cout<<"The minimum possible digitsum after adding the number is "<<findMinDigitSum(n, d);
    return 0;
}

出力

The minimum possible digitsum after adding the number is 1

計算量

ループは最大でも 8 回しか実行されないため、時間計算量・空間計算量はいずれも O(1) です。入力の大きさに関わらず一定の計算量で答えを導ける点が、この手法の大きな利点です。