C++で解く：すべての桁が一意（重複なし）となる、n未満の最大の数を出力するアルゴリズム

問題概要

この問題では、整数 n が与えられます。求めるのは、「n より厳密に小さい数のうち、すべての桁が互いに異なる（重複がない）最大の数」です。

具体例を使って問題を理解しましょう。

入力: n = 2332
出力: 2319

2332 未満の数の中で、桁の重複がない最大の数は 2319 となります。

解法のアプローチ

この問題は、以下のようなシンプルな戦略で解くことができます。

1. n − 1 から 0 へ逆順にカウントダウンしていきます。
2. 各数値について各桁の出現回数を記録し、すべての桁が一度しか現れていないかどうかを判定します。
3. 条件を満たす数値が見つかった時点でそれを出力してループを終了します。
4. 条件を満たさなければ、次の数値の判定へと進みます。

答えとなる数は必ず n 未満の範囲に存在するため、ループの最大実行回数は常に n 回未満に収まります。

C++による実装例

上記の解法を実装したプログラムが以下です。

#include <bits/stdc++.h>
using namespace std;
int findDistinctDigitNumber(int n) {
    for (int i = n - 1; i>=0 ; i--) {
        int count[10] = { 0 };
        int x = i;
        int count1 = 0, count2 = 0;
        while (x) {
            count[x % 10]++;
            x /= 10;
            count1++;
        }
        for (int j = 0; j < 10; j++) {
            if (count[j] == 1)
                count2++;
        }
        if (count1 == count2)
        return i;
    }
}
int main() {
    int n = 44324;
    cout<<"Number less than "<<n<<" with all digits distinct are : "<<findDistinctDigitNumber(n);
    return 0;
}

コードのポイント

• count[10] 配列で、各桁（0〜9）の出現回数をカウントします。
• count1 は総桁数、count2 は「ちょうど1回だけ現れた桁」の種類数です。
• count1 == count2 が成立するとき、その数はすべての桁が一意であることを意味します。

実行結果

Number less than 44324 with all digits distinct are : 43987

このように、44324 未満で桁の重複がない最大の数として 43987 が出力されます。

計算量について

最悪の場合、答えが見つかるまで O(n × d) の時間がかかる可能性があります（d は桁数）。ただし実際には、桁が重複しない数は比較的密に存在するため、多くの場合はごく短い探索で答えが見つかります。