计算 1 到 N 的整数中 0 出现的次数

Question

如何有效地计算 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 之间”的方法。我们可以通过看到某种模式来做吗？

我们不能扩展logic compiled here吗？解决这个问题？

Answer 1

更新的答案

我最初的回答很容易理解，但编码起来却很棘手。这是更容易编码的东西。这是一种直接的非递归解决方案，通过计算零在每个位置出现的方式的数量来工作。

例如:

x <= 1234. How many numbers are there of the following form?

x = ??0?

“数百或更多”有 12 种可能性 (1,2, ..., 12)。然后必须有一个零。那么最后一位数有10种可能。这将给出 12 * 10 = 120 个数字，其中第三位为 0。

因此范围(1 到 1234)的解决方案是:

• ?0??: 1 * 100 = 100
• ??0?: 12 * 10 = 120
• ???0: 123
• 总计 = 343

但如果 n 包含零数字，则异常(exception)。考虑以下情况:

x <= 12034. How many numbers are there of the following form?

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