C++で数値が1桁になるまでの桁の合計と積の最大値を求める方法

本記事では、与えられた数値が1桁になるまで各桁の合計および積を繰り返し計算し、その結果の最大値を求めるC++プログラムについて解説します。

問題の概要

任意の整数が与えられたとき、次の2つの処理を実行します。

• 繰り返し合計(デジタルルート): 各桁の数字を合計し、結果が1桁になるまでこの操作を繰り返します。
• 繰り返し積(乗法的デジタルルート): 各桁の数字を乗算し、結果が1桁になるまでこの操作を繰り返します。

その後、2つの結果を比較し、大きい方の値を出力します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
// 加算によって数値を1桁に変換する
long repeatedSum(long n) {
    if (n == 0)
        return 0;
    return (n % 9 == 0) ? 9 : (n % 9);
}
// 乗算によって数値を1桁に変換する
long repeatedProduct(long n) {
    long prod = 1;
    while (n > 0 || prod > 9) {
        if (n == 0) {
            n = prod;
            prod = 1;
        }
        prod *= n % 10;
        n /= 10;
    }
    return prod;
}
// 最大値を求める
long maxSumProduct(long N) {
    if (N < 10)
        return N;
    return max(repeatedSum(N), repeatedProduct(N));
}
int main() {
    long n = 631;
    cout << maxSumProduct(n) << endl;
    return 0;
}

出力

8

コードの解説

repeatedSum関数

この関数は、デジタルルートの数学的性質を利用しています。正の整数を9で割った余りが0の場合は9、それ以外の場合はその余り自体が1桁に還元した結果と一致します。これにより、ループ処理を一切使わずにO(1)で計算できます。

repeatedProduct関数

この関数は、各桁の積を計算します。入力の桁を使い切っても結果が9を超えている場合は、その積を新たな入力として再度各桁の積を計算します。この処理を結果が1桁になるまで繰り返します。

maxSumProduct関数

入力がすでに1桁の場合はその値をそのまま返し、2桁以上の場合は上記2つの関数の結果のうち大きい方を返します。

実行例の確認

n = 631 の場合を考えてみましょう。

• 合計の場合: 6 + 3 + 1 = 10 → 1 + 0 = 1
• 積の場合: 6 × 3 × 1 = 18 → 1 × 8 = 8

したがって、max(1, 8) = 8 が出力されます。

計算量

repeatedSumはO(1)、repeatedProductは1回の反復で桁数に比例した処理を行うため、全体の計算量はO(log N)程度に収まります。非常に大きな数でも効率的に処理できる実装です。