このアルゴリズムを基数 2 から基数 10 に適応させることをお勧めします。
範囲内の整数の 2 の補数バイナリ表現における 1 の数
結果のアルゴリズムは O(log N) です。
count(n)
アプローチは、1 から までのゼロをカウントする単純な再帰関数を作成することn
です。
重要な観察事項は、N が 9 で終わる場合です。たとえば、次のようになります。
123456789
0 から N までの数字を 10 個の同じサイズのグループに入れることができます。グループ 0 は 0 で終わる数字です。グループ 1 は 1 で終わる数字です。グループ 2 は 2 で終わる数字です。同様に、9 で終わるすべての数字であるグループ 9 まで続きます。
グループ 0 を除く各グループcount(N/10)
は、ゼロで終わるものがないため、合計にゼロ桁が含まれます。グループ 0 は、(count(N/10)
最後の数字以外のすべての数字をカウントする) プラスN/10
(最後の数字からゼロをカウントする) に寄与します。
0 から N ではなく 1 から N に移動するため、このロジックは 1 桁の N に当てはまらないため、これを特殊なケースとして扱います。
[アップデート]
count(n, d)
一体、その数字が 1 から までの数字の中で何回d
出現するかを一般化して定義しましょうn
。
/* Count how many d's occur in a single n */
unsigned
popcount(unsigned n, unsigned d) {
int result = 0;
while (n != 0) {
result += ((n%10) == d);
n /= 10;
}
return result;
}
/* Compute how many d's occur all numbers from 1 to n */
unsigned
count(unsigned n, unsigned d) {
/* Special case single-digit n */
if (n < 10) return (d > 0 && n >= d);
/* If n does not end in 9, recurse until it does */
if ((n % 10) != 9) return popcount(n, d) + count(n-1, d);
return 10*count(n/10, d) + (n/10) + (d > 0);
}
このケースの醜さはn < 10
、範囲がn
0 ~ ではなくn
1 ~ であるn
ことから来ています。d
d
このソリューションを非再帰ループに変換することは、(a) 些細なことであり、(b) 不要であり、(c) 読者の演習として残されています。
【アップデート2】
最終項も、0 から ではなく(d > 0)
1 から の範囲に由来します。末尾が 9 の場合、1 から 1 までの範囲で末尾の数字が 1桁の数字はいくつありますか? がゼロの場合、答えは; がゼロ以外の場合、値自体が含まれているため、それよりも 1 大きくなります。n
n
n
n
d
d
n/10
d
d
たとえば、n
が 19 でd
が 0 の場合、0 で終わる小さい数字は 1 つしかありません (つまり、10)。しかし、n
が 19 でd
が 2 の場合、2 で終わる小さい数が 2 つあります (つまり、2 と 12)。
コメントでこのバグを指摘してくれた @Chan に感謝します。コードで修正しました。