你如何有效地计算从1到N的整数的十进制表示中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之间".我们可以通过看到某种模式来做到吗？
Mar*_*ers 17
更新的答案
我原来的答案很容易理解,但很难编码.这里的代码更简单.这是一个直接的非递归解决方案,通过计算零在每个位置出现的方式来工作.
例如:
x <= 1234.以下表格中有多少个数字？
x = ?? 0？
"数百或更多"(1,2,...,12)有12种可能性.然后一定是零.然后最后一位数有10种可能性.这给出12 * 10 = 120了在第三个数字处包含0的数字.
因此,范围(1到1234)的解决方案是:
但是例外是如果n包含零数字.考虑以下情况:
x <= 12034.以下表格中有多少个数字？
x = ?? 0 ??
我们有12种方法可以选择"数千甚至更多".对于1,2,... 11,我们可以选择任意两个最后的数字(给出11*100种可能性).但是,如果我们开始与12,我们只能选择之间的数字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到0的零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(从最终数字开始计算零).
由于我们从1到N而不是0到N,这个逻辑分解为单位数N,所以我们只是将其作为一个特例来处理.
[更新]
究竟发生了什么,让我们概括和定义count(n, d)为数字多少次d出现1至数之中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再次来自范围是1 n而不是0到n......对于任何n大于或等于d的单位数,除非d为零,否则计数为1 .
将此解决方案转换为非递归循环是(a)无关紧要,(b)不必要,以及(c)留给读者的练习.
[更新2]
最后一个(d > 0)术语也来自范围是1 n而不是0到n.当n以9结尾时,1和n包含的数字之间有d多少个数字？那么,当d为零时,答案是n/10; 当d非零时,它不止于此,因为它包含值d本身.
例如,如果n是19且d为0,则只有一个较小的数字以0结尾(即10).但如果n是19并且d是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都在范围内，每十个最后一位数字都是 0，所以这是k零，每个前缀j（除了最后一位数字）出现十次，但我们不能算 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
}