C++で解く：N以下の重複した桁を含む整数の個数の求め方

問題の概要

正の整数 N が与えられたとき、N以下の正の整数の中に、少なくとも1つの重複した桁（同じ数字が2回以上現れる）を含む数がいくつあるかを求める問題です。

例として、入力が 99 の場合を考えてみましょう。このときの出力は 9 となります。該当するのは 11, 22, 33, 44, 55, 66, 77, 88, 99 の9個だからです。

解法のアプローチ

すべての数を1つずつ確認するのは非効率です。そこで視点を変え、「重複した桁を一切含まない数」の個数を組み合わせ論的に数え上げ、それを N から引くことで高速に答えを得られます。

具体的には、次の手順で進めます。

• 関数 A(m, n) の定義：m × (m−1) × … × (m−n+1) を計算して返します。これは重複なしで数字を選んで並べる場合の数（順列）に対応します。
• 桁の分解：N + 1 を1桁ずつ取り出し、配列 arr に先頭から格納します。
• 初期化：結果用の変数 ret := 0、桁数 n := arr のサイズ とします。
• 桁数が n 未満の数の集計：i 桁（1 ≤ i < n）の重複なしの数は 9 × A(9, i−1) 個なので、これを ret に加算していきます。
• 桁数が n と同じ数の集計：集合 visited で使用済みの数字を管理しながら、上位の桁から順に処理します。
  • 各桁位置 i について、その桁より小さい数字 j を先頭（最上位桁の場合は1から開始）に置いた場合の組み合わせ A(9 − i, n − i − 1) を ret に加算します。ただし、j が既に使用済みの場合はスキップします。
  • 現在の桁 digit がすでに visited に存在する場合はループを抜けます（これ以上、共通の接頭辞を持つ重複なしの数は存在しないため）。
  • そうでなければ、digit を visited に追加します。
• 答えの算出：最後に N − ret を返します。

C++での実装例

以下のコードで実際の実装を確認できます。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int A(int m, int n){
        int ret = 1;
        for (int i = 0; i < n; i++) {
            ret *= m;
            m--;
        }
        return ret;
    }
    int numDupDigitsAtMostN(int N){
        vector<int> arr;
        for (int i = N + 1; i > 0; i /= 10) {
            arr.insert(arr.begin(), i % 10);
        }
        int ret = 0;
        int n = arr.size();
        for (int i = 1; i < n; i++) {
            ret += 9 * A(9, i - 1);
        }
        set<int> visited;
        for (int i = 0; i < n; i++) {
            int digit = arr[i];
            for (int j = i == 0 ? 1 : 0; j < digit; j++) {
                if (visited.count(j))
                    continue;
                ret += A(9 - i, n - i - 1);
            }
            if (visited.count(digit))
                break;
            visited.insert(digit);
        }
        return N - ret;
    }
};
main(){
    Solution ob;
    cout << (ob.numDupDigitsAtMostN(99));
}

入力

99

出力

9

まとめ

この手法では、Nの桁数を d としたとき、各桁で最大10通りの分岐しか発生しないため、極めて高速に答えを求められます。単純な全探索では処理しきれない大きな N に対しても有効で、競技プログラミングなどでもよく使われる「桁DP・組み合わせ数え上げ」の代表的なパターンと言えます。