C++で実装する！N未満で桁の和がNより大きい最大の数を求めるアルゴリズム

このチュートリアルでは、「Nより小さい数のうち、桁の和がNの桁の和よりも大きくなる最大の数」を求めるプログラムをC++で作成します。

問題の例

例えば、N = 75 の場合を考えてみましょう。75の桁の和は 7 + 5 = 12 です。このとき、75未満の数の中で桁の和が12を超える最大の数は 69(6 + 9 = 15)となります。

解決手順

• 桁の和を求める関数を作成します。
• Nを初期化します。
• n - 1 から 1 まで順に調べるループを記述します。
  • 現在の数の桁の和とNの桁の和を比較します。
  • 現在の数の桁の和の方が大きければ、その数を返します。
  • 条件を満たさなければ、次の数へ進みます。

コード例

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

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

// 桁の和を計算する関数
int sumOfDigits(int n) {
    int digitsSum = 0;
    while (n > 0) {
        digitsSum += n % 10;
        n /= 10;
    }
    return digitsSum;
}

// 条件を満たす最大の数を探す関数
int findLargestNumber(int n) {
    int i = n - 1;
    while (i > 0) {
        if (sumOfDigits(i) > sumOfDigits(n)) {
            return i;
        }
        i--;
    }
    return -1;
}

int main() {
    int n = 75;
    cout << findLargestNumber(n) << endl;
    return 0;
}

出力

上記のコードを実行すると、以下の結果が得られます。

69

コードの解説

sumOfDigits 関数: 数値を10で割った余りを順番に取り出して各桁の数字を取得し、その合計を計算します。n が0になるまで繰り返すことで、すべての桁の和が求まります。

findLargestNumber 関数: n - 1 から降順に調べていく線形探索を行います。条件(桁の和がNより大きい)を満たした時点ですぐにその数を返すため、最初に見つかった数が自動的に「最大の数」になります。

計算量について

このアルゴリズムの時間計算量は O(N log N) です。1つの数値の桁和の計算には桁数分(O(log N))の処理が必要で、それを最大でN回繰り返すためです。ただし、桁和の性質上、条件を満たす数は比較的早く見つかることが多く、実用上は十分高速に動作します。

まとめ

このチュートリアルでは、N未満の数の中で桁の和がNより大きい最大の数を求める方法を学びました。シンプルな線形探索で実装できますが、桁DPなどのテクニックを活用すれば、さらなる効率化も可能です。本チュートリアルについてご不明な点がありましたら、コメント欄でお気軽にお知らせください。