1からNまでの整数の10進表現で0の出現数を効率的にカウントするにはどうすればよいですか？
e.g. The number of 0's from 1 to 105 is 16. How?
10,20,30,40,50,60,70,80,90,100,101,102,103,104,105
0の数を数えると16になります。
明らかに、ブルートフォースアプローチは評価されません。「1からNまでの数字の数」に依存しないアプローチを考え出す必要があります。ある種のパターンを見ただけでできるのでしょうか？
ここでコンパイルされたロジックを拡張して、この問題を解決することはできませんか？
更新された回答
私の最初の答えは、理解するのは簡単でしたが、コーディングするのは難しいものでした。これは、コード化がより簡単なものです。これは、ゼロが各位置に現れる方法の数を数えることによって機能する、単純な非再帰ソリューションです。
例えば：
x <= 1234. 次の形式の数はいくつありますか?
x = ??0?
「数百以上」には 12 の可能性があります (1、2、...、12)。次に、ゼロが必要です。次に、最後の桁には 10 の可能性があります。これにより12 * 10 = 120、3 桁目に 0 を含む数値が得られます。
したがって、範囲 (1 ～ 1234) の解は次のようになります。
nただし、ゼロの数字が含まれている場合は例外です。次のケースを検討してください。
x <= 12034. 次の形式の数はいくつありますか?
x = ??0??
「千以上」を選択する方法は 12 通りあります。1、2、... 11 の場合、任意の最後の 2 桁を選択できます (11 * 100 の可能性があります)。しかし、12 から始めると、最後の 2 桁の00との間の数字しか選択できません。34だから私たちは11 * 100 + 35完全に可能性を得ます。
以下は、このアルゴリズムの実装です (Python で書かれていますが、C に簡単に移植できるはずです)。
def countZeros(n):
result = 0
i = 1
while True:
b, c = divmod(n, i)
a, b = divmod(b, 10)
if a == 0:
return result
if b == 0:
result += (a - 1) * i + c + 1
else:
result += a * i
i *= 10
このアルゴリズムを基数 2 から基数 10 に適応させることをお勧めします。
結果のアルゴリズムは 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、範囲がn0 ～ ではなくn1 ～ であるnことから来ています。dd
このソリューションを非再帰ループに変換することは、(a) 些細なことであり、(b) 不要であり、(c) 読者の演習として残されています。
【アップデート2】
最終項も、0 から ではなく(d > 0)1 から の範囲に由来します。末尾が 9 の場合、1 から 1 までの範囲で末尾の数字が 1桁の数字はいくつありますか? がゼロの場合、答えは; がゼロ以外の場合、値自体が含まれているため、それよりも 1 大きくなります。nnnnddn/10dd
たとえば、nが 19 でdが 0 の場合、0 で終わる小さい数字は 1 つしかありません (つまり、10)。しかし、nが 19 でdが 2 の場合、2 で終わる小さい数が 2 つあります (つまり、2 と 12)。
コメントでこのバグを指摘してくれた @Chan に感謝します。コードで修正しました。
しましょうZ(n) = #zero digits in numbers 0 <= k < n。明らかに、Z(0) = 0.
の場合n = 10*k + r, 0 <= r <= 9、すべての10*k数値10*j + s, 0 <= j < k, 0 <= s <= 9が範囲内にある場合、最後の 10 桁目はそれぞれ 0 であるため、kゼロであり、各プレフィックスj(最後の桁を除くすべて) は 10 回発生しますが、0 をカウントしてはならないため、プレフィックスのゼロの数はです10*(Z(k)-1)。
数字のゼロのr数10*k, ..., 10*k + (r-1)はr*number of zeros in k + (r > 0 ? 1 : 0)です。
O(log n)計算するためのアルゴリズムがありますZ(n)
unsigned long long Z(unsigned long long n)
{
if (n == 0) {
return 0;
}
if (n <= 10) {
return 1;
}
unsigned long long k = n/10, r = n%10;
unsigned long long zeros = k + 10*(Z(k)-1);
if (r > 0) {
zeros += r*zeroCount(k) + 1;
}
return zeros;
}
unsigned zeroCount(unsigned long long k)
{
unsigned zeros = 0;
while(k) {
zeros += (k % 10) == 0;
k /= 10;
}
return zeros;
}
任意の範囲の数値を計算するには、
unsigned long long zeros_in_range(unsigned long long low, unsigned long long high)
{
return Z(high+1) - Z(low); // beware of overflow if high is ULLONG_MAX
}
私がこの問題にアプローチした方法：
数値は 1 から N の範囲で指定できます。
だから、私はこれを次のような範囲に分けました：
Rangle : #Digits : #Zeros
1 - 9 : 1 : 0
10 - 99 : 2 : 9 (number of all the possible digits when zero is at units place=> _0 ie, 1,2,3,4,5,6,7,8,9
100 - 199 : 3 : 20 => 10 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
200 - 276 : 3 : 18 => 8 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
300 - 308 : 3 : 10 => 1 (#digits when zero is at units place) + 9 (#digits when zero is at tens place)
1000- 1008: 4 : 19 => 1 + 9 + 9
任意の範囲 1 ～ N について、数値をこれらの範囲に分割し、上記のロジックを使用してゼロの数を計算できるようにしたいと考えています。
テスト走行：
与えられた数 N に対して:
- compute number of digits: len
- if len = 1 : d1: return 0
- len = 2: d2_temp: count # of digits that can possibly occur when 0 is at unit's place
: for e.g. 76: so numbers can be between 10 - 76: (7 - 1) + 1 = 7
: d2: sum(d2_temp, d1)
- len = 3: return d3 : sum(d3_temp, d2)
: compute d3_temp:
: for e.g. n = 308 : get digit at 10^(len-1) : loopMax 3
: d3_temp1: count number of zeros for this loop: 1 * 100 to (loopMax -1) * 100 : (loopMax-1) * 20
: d3_temp2: for n count (#digits when zero is at units place) + (#digits when zero is at tens place)
: d3_temp = d3_temp1 + d3_temp2
一般化してみましょう：
99 : sum( , )
: d3_temp:
: loopMax: n = 99 : n/(10^1) : 9
: d3_temp1: 8 : (9-1) * (10*(len-1)) : (loopMax - 1) * 10 * (len-1)
: d3_temp2: 1 : for len, count #0s in range (loopMax * 10 * (len-1)) to n : count(90, 99)
: d3_temp = 8 + 1
: sum(9, 0)
: 9
ここから先に進むのに問題がありますが、これでうまくいきます。