C++でn以下の整数のうち同じ数字を複数含む数を数えるプログラム

問題概要

整数 n が与えられたとき、「n 以下の正の整数の中で、少なくとも1つの桁が2回以上現れる数」の個数を求めます。

例えば n = 200 の場合、答えは 38 になります。実際には、11・22・…・99 のような2桁の数が9個、100〜199 の範囲で同じ数字を含むものが28個、さらに 200 自身(0が2つ含まれる)の合計38個となるためです。

解法の考え方:補集合を利用した数え上げ

「重複した桁を持つ数」を直接数えるのは複雑ですが、その補集合、つまり「すべての桁が互いに異なる数」の個数を数えて全体から引けば、簡単に求められます。

答え = n −(n 以下の、全桁が異なる正整数の個数)

アルゴリズムの手順

1. n を上の桁から順に配列 a に格納します(例：200 → [2, 0, 0])。
2. ret を n で初期化します。
3. n より桁数が少ない「全桁相異なる数」を数えて ret から引きます。w 桁の数では、先頭の桁は9通り(1〜9)、2番目も9通り、3番目以降は 8・7・… と減っていくため、累積変数 d に min(9, 10 − w + 1) を掛けていきます。
4. n と同じ桁数で n 以下の「全桁相異なる数」を数える関数 go() を定義します。
   • b は「使用済みの桁」を管理するビットマスクです(初期値では全桁が未使用)。
   • 各桁 i について、a[i] より小さい未使用の数字をその位置に固定した場合、残りの桁は自由に選べるため、その組み合わせ数(10 − j の積)を ret から差し引きます。なお、最上位桁(i = 0)では先頭に 0 を置けないため、ループ変数 d は 1 から開始する点に注意してください。
   • a[i] 自体が未使用ならビットマスクに登録して次の桁へ進み、すでに使われている場合は、それ以降に全桁相異なる数は存在しないため処理を終了します。
5. ループが最後まで完了した場合は n 自身が全桁相異なる数なので、ret を1減らします。
6. go() を呼び出し、ret を返します。

C++での実装例

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

int solve(int n) {
    vector<int> a;
    // n を上の桁から順に配列へ格納
    for (int x = n; x; x /= 10) a.push_back(x % 10);
    reverse(a.begin(), a.end());

    int ret = n;

    // 桁数が n より少ない「全桁相異なる数」を引く
    for (int w = 1, d = 1; w < a.size(); ++w) {
        d *= min(9, 10 - w + 1);
        ret -= d;
    }

    // n と同じ桁数で n 以下の「全桁相異なる数」を引く
    auto go = [&]() {
        int b = (1 << 10) - 1; // 使用済み桁のビットマスク
        for (int i = 0; i < a.size(); ++i) {
            // i 桁目を a[i] 未満の未使用数字に固定した場合の数を引く
            for (int d = (i < 1); d < a[i]; ++d) {
                int x = 0;
                if ((1 << d) & b) ++x;
                for (int j = i + 1; j < a.size(); ++j) x *= 10 - j;
                ret -= x;
            }
            // a[i] を使用済みにする(既に使われていれば終了)
            if ((1 << a[i]) & b)
                b ^= (1 << a[i]);
            else
                return;
        }
        --ret; // n 自身が全桁相異なる場合の調整
    };
    go();
    return ret;
}

int main() {
    cout << solve(200) << endl;
    return 0;
}

実行結果

入力

200

出力

38

計算量

n の桁数を D とすると、時間計算量は O(D²)、空間計算量は O(D) です。桁数にのみ依存するため、非常に大きな n に対しても高速に動作します。