计数出现的0的整数从1到N的数量 [英] Count the number of occurrences of 0's in integers from 1 to N

问题描述

您将如何有效地计算在小数重$ P $ 1的整数到N psentation出现0的数？

How will you efficiently count number of occurrences of 0's in the decimal representation of integers from 1 to N?

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。

Count the number of 0's & you will find it 16.

显然，蛮力的做法会不会AP preciated。你必须拿出不依赖于有多少数字1间下降到N的做法。 我们可以通过查看某种模式只是做？

Obviously, a brute force approach won't be appreciated. You have to come up with an approach which doesn't depend on "How many numbers fall between 1 to N". Can we just do by seeing some kind of pattern?

我们不能扩展这里编译逻辑来工作这个问题？

Cannot we extend the logic compiled here to work for this problem?

推荐答案

更新答案

我最初的回答很简单理解，但棘手的code。这里的东西是简单code。这是一个直接的非递归的解决方案，它通过计算的方式零点能出现在每一个位置的数字。

My original answer was simple to understand but tricky to code. Here's something that is simpler to code. It's a straight-forward non-recursive solution that works by counting the number of ways zeros can appear in each position.

例如：

X - LT; = 1234，有多少数字是以下形式的有

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

X =δλ0？

有12的可能性为数百或更多（1,2，...，12）。那么就必须有一个零。然后有10的可能性的最后一位数字。这给 12 * 10 = 120 包含0在第三位的数字。

There are 12 possibilities for the "hundreds or more" (1,2, ..., 12). Then there must be a zero. Then there are 10 possibilities for the last digit. This gives 12 * 10 = 120 numbers containing a 0 at the third digit.

因此​​为范围（1至1234）的解决方案是：

The solution for the range (1 to 1234) is therefore:

• 0 ??：？1 * 100 = 100
• ？0？：12 * 10 = 120
• ??? 0：123
• 在总= 343

但一个例外是，如果 N 包含了一个数字零。考虑以下情况：

But an exception is if n contains a zero digit. Consider the following case:

X - LT; = 12034.多少个数字有以下几种形式存在。

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 的可能性。

We have 12 ways to pick the "thousands or more". For 1, 2, ... 11 we can choose any two last digits (giving 11 * 100 possibilities). But if we start with 12 we can only choose a number between 00 and 34 for the last two digits. So we get 11 * 100 + 35 possibilities altogether.

下面是该算法的实现（用Python编写的，但在某种程度上，应该是很容易地移植到C）：

Here's an implementation of this algorithm (written in Python, but in a way that should be easy to port to 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

这篇关于计数出现的0的整数从1到N的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！