JavaScriptで一意な数字のみで構成されるn桁までの数字を数える方法

問題

JavaScriptで次のような関数を実装することを考えます。引数として数値 num を1つだけ受け取り、「num桁までの数字の中で、すべての桁が一意（重複なし）であるもの」の個数を返します。

例えば、関数への入力が次の場合：

const num = 1;

出力は次のようになります：

const output = 10;

出力の説明

0、1、2、3、4、5、6、7、8、9 の10個の数字は、いずれも1桁であり、それぞれに数字の重複がないためです。

実装例

const num = 1;
const uniqueDigits = (num = 1) => {
    const dp = [1, 10];
    const sum = [1, 11];
    for (let i = 2; i <= num; i++) {
        dp[i] = sum[i - 1] + (10 - i) * (dp[i - 1]);
        sum[i] = sum[i - 1] + dp[i];
    };
    return dp[num];
};
console.log(uniqueDigits(num));
console.log(uniqueDigits(2));
console.log(uniqueDigits(3));

コードの解説

この実装では動的計画法（Dynamic Programming）を採用しています。すでに計算済みの小さな桁数の結果を再利用することで、すべてを数え直すことなく効率的に答えを求められるのがポイントです。

• dp：dp[i] に「i桁までの、すべての桁が一意な数字の総数」を格納します。初期値は dp[0] = 1、dp[1] = 10 です。
• sum：dp の累積和を保持する補助配列で、漸化式の計算に使用されます。
• 漸化式：桁を追加していくたびに使える残りの数字の選択肢が減っていくため、その減少分を係数 (10 - i) として反映しています。

処理はループを1回回すだけなので、時間計算量は O(n) と非常に効率的です。

実行結果

コンソールには次のように出力されます：

10
91
739

• num = 1 の場合：0〜9 の10個
• num = 2 の場合：1桁と2桁を合わせて91個（例：12、43 など。ただし 11 や 22 のように同じ数字が並ぶものは除外）
• num = 3 の場合：3桁までを合わせて739個