C++で指定した桁数と桁の合計を満たす最大の数を求める方法

問題の概要

この問題では、2つの整数値が与えられます。1つは数値の桁数を表す N、もう1つは桁の合計を表す sum です。目的は、指定された桁数と桁の合計を満たす最大の数を見つけることです。

具体例で問題を確認しましょう。

入力 : N = 3, sum = 15
出力 : 960

3桁の数のうち、桁の合計が15になる最大の数は 960 です(9 + 6 + 0 = 15)。

解法1: 全探索(ブルートフォース)

最も単純なアプローチは、N桁のすべての数を大きい方から小さい方へ順に走査し、桁の合計を計算して、sum と一致した時点でその数を返す方法です。

実装例

#include <iostream>
using namespace std;
int digitSum(int n){
    int sum = 0;
    while(n){
        sum += n%10;
        n = n/10;
    }
    return sum;
}
int findLargestNumWithSum(int N, int sum){
    if (sum == 0){
        if(N == 1)
            return -1;
        else
            return -1;
    }
    if (sum > 9*N){
        return -1;
    }
    int num = 1;
    for(int i = 0; i < N; i++)
        num *= 10;
    while(1){
        if(digitSum(num) == sum){
            return num;
        }
        num -- ;
        if(num == 0)
            return -1;
    }
}
int main(){
    int sum = 25, N = 3;
    cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<< findLargestNumWithSum(N, sum);
    return 0;
}

出力

The largest 3 digit number with sum 25 is 997

この方法は確実に正解を得られますが、N桁の候補を1つずつ確認するため、計算量は O(N × 10^N) 程度になります。N が大きくなると処理時間が急増するため、実用的とは言えません。

解法2: 貪欲法(グリーディーアプローチ)

より効率的なのが貪欲法です。最上位桁(MSB)から順に、「その桁に置ける最大の数字」を配置し、sum からその値を差し引いていきます。この操作を N 桁分繰り返すことで、求める数が得られます。

具体的には、残りの sum が 9 以上であれば現在の桁に 9 を置き、9 未満であれば sum の値をそのまま配置します。この処理を最上位桁から最下位桁(LSB)まで繰り返すのがポイントです。

実装例

#include <iostream>
using namespace std;
int findLargestNumWithSum(int N, int sum){
    if (sum == 0){
        if(N == 1)
            return -1;
        else
            return -1;
    }
    if (sum > 9*N){
        return -1;
    }
    int num = 0;
    for (int i = 0; i < N; i++){
        if (sum >= 9){
            num += 9;
            sum -= 9;
            if(i < (N - 1)){
                num *= 10;
            }
        }
        else{
            num += sum;
            sum = 0;
            if( i < (N - 1))
                num *= 10;
        }
    }
    return num;
}
int main(){
    int sum = 25,
    N = 3;
    cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<<findLargestNumWithSum(N, sum);
    return 0;
}

出力

The largest 3 digit number with sum 25 is 997

貪欲法では各桁を1回ずつ処理するだけでよいため、計算量は O(N) と非常に効率的です。また、sum が 9×N を超える場合など解が存在しない入力に対しては -1 を返すことで、不正なケースにも対応しています。大きな N を扱う場合は、貪欲法の採用が望ましいと言えるでしょう。