C++で一意の桁（重複しない数字）を持つ数を数える方法

負でない整数 n が与えられたとき、0 以上 10ⁿ 未満の範囲に存在する「すべての桁が一意（重複なし）」である数 x の個数を求める問題を考えてみましょう。

例えば n = 2 の場合、0 から 100 未満までの数のうち、11、22、33、44、55、66、77、88、99 のように同じ数字が重複している数を除外した個数、つまり 91 が答えとなります。

解法のアプローチ

この問題は、桁ごとに選べる数字の組み合わせを順番にかけていくことで効率的に解くことができます。手順は以下の通りです。

• n が 0 の場合は 1 を返します（0 のみが該当するため）。

• n は最大でも 10 桁しか考慮できないため、n := min(10, n) とします。

• n が 1 の場合は 10 を返します（0〜9 の一桁の数はすべて一意であるため）。

• 初期値として ans := 9、ret := 10 を設定します。最初の桁には 1〜9 の 9 通り、全体としては 0〜9 の 10 個が該当するためです。

• i を 2 から n までループさせます。

  • ans := ans * (9 − i + 2) として、新しい桁で使える残りの数字の選択肢を掛け合わせます。

  • ret := ret + ans として累積和を更新します。

• 最後に ret を返します。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int countNumbersWithUniqueDigits(int n) {
      if(n == 0)return 1;
      n = min(10, n);
      if(n == 1)return 10;
      int ans = 9;
      int ret = 10;
      for(int i = 2; i<= n; i++){
         ans *= (9 - i + 2);
         ret += ans;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.countNumbersWithUniqueDigits(3));
}

入力例

3

出力例

739

この実装では、n = 3 の場合に 739 という結果が得られます。これは 0 から 999 までの数のうち、同じ数字が 2 回以上現れない数の総数です。計算量は O(n) と非常に効率的であり、n が大きくなっても高速に動作します。