统计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之间有多少个数字”的方法。我们能否通过观察某种模式来解决这个问题？

难道我们不能将这里编译的逻辑扩展到这个问题上吗？

- Green goblin

---

我认为你不应该在面试后泄露那些问题 ;) - Mateusz Dymczyk

@DeadMG，我觉得更可能是N log N的顺序。 - Jens Gustedt

我喜欢这类问题。该算法在课堂外的实际应用机会为0.00000000000000000000000000001%。 - Tony Hopkinson

为了在一个范围内分配数字，计数是有帮助的。参考Benford定律。 - Alex Reynolds

请查看在0和N之间计算K的数量？。 - herohuyongtao

Answer 1

更新的答案

我的原始答案很容易理解，但编码有些棘手。这里提供了一个更简单的编码方法。这是一个直接的非递归解决方案，通过计算每个位置上零的出现方式数量来工作。

例如：

x <= 1234。有多少个以下形式的数字？

x = ??0?

"百位或更高"（1、2、...、12）有12种可能性。然后必须有一个零。最后一位有10种可能性。这给出了包含第三个数字为0的数字数目为12 * 10 = 120。

因此，范围（1到1234）的解决方案如下：

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

但是，如果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

- Mark Byers

---

对于1到999，你的“结束条件的特殊处理”覆盖了90%的范围（100到999）。这不是一个很好的答案... - Nemo

@Nemo，我认为你误解了那部分。规则是将数字分成具有相等位数的范围，因此[1,999]变成([1,9],[10,99],[100,999])，然后对于每个段，您可以执行(high-low)*(length-1)/10，并将它们加在一起。 "特殊处理结束条件"是如果我们不是[1,999]这样的东西，而是[1,1234]之类的东西，其中[1000,1234]不符合模式。只有最后一部分需要特殊处理。 - Kevin

@Kevin：是的，我本来在想要不要选择 (1,666) 或者什么的，但最终我还是赌大了，超出了我的范围。 - Nemo

@Mark：好的，那就把它编写出来，这样我们就可以将其与其他解决方案进行比较 :-) - Nemo

现在您已经提供了代码并进行了调试，我将取消我的反对票。我仍然认为递归公式更简单，但我同意这个方法可行。顺便说一下，@drewk的“期望”可能更好地称为“给出正确答案”。 - Nemo

Answer 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（计算最后一位中的零）。

由于我们从1到N而不是从0到N，所以这种逻辑在单位数N时会失效，因此我们将其作为特殊情况处理。

[更新]

让我们来概括并定义count(n, d)，表示从1到n的数字中数字d出现的次数。

/* 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);
}

案例中的丑陋之处再次来自于范围为1到n而不是0到n... 对于任何大于或等于d的一位数n，计数为1，除非d为零。

将此解决方案转换为非递归循环是(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在评论中指出此漏洞。我已在代码中修复了它。

- Nemo

---

@Nemo，我发布了一个解决方案，我认为它与您建议的类似。我正在努力将我的解决方案泛化。你能帮我吗？谢谢。 - brainydexter

@Nemo：你测试过你的解决方案吗？当 n = 20 且 d = 2 时，有3个2（2、12、20），但是你的解决方案只得到了2个。 - roxrook

@Chan：确实，当d不为零时我有一个bug。已修复，谢谢。 - Nemo

Answer 3

令Z(n) = #小于n的数字中0的个数，显然，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)中0的数量为r*数字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
}

- Daniel Fischer

---

@BLUEPIXY 忘记减去前导0，感谢你提醒。 - Daniel Fischer

@BLUEPIXY 不，344是正确的，Prelude> length . filter (== '0') $ [0 .. 1233] >>= show会得到344。Z(n)计算0, 1, ..., n-1中的零的个数，因此对于所有n > 0，它必须至少为1。 - Daniel Fischer

Answer 4

我有一种非常简单的方法来计算 1 到 n 之间的零数。 希望这能解决你的问题并减少复杂性。

function countZero(n) {
  var count = 0;
  while (n > 0) {
    count += Math.floor(n / 10);
    n = n / 10;
  }
  console.log(count);
}

countZero(99);

- Divya Ranjana

Answer 5

# in single loop without using inbuilt functions

def func(n):
  lst=list(range(0,n+1)) #make list from 0 to n

  strng=str(lst) #convert list into string

  strng=strng[1:-1] #remove first and last square braces from string

  strng=strng.replace(",","") #remove commas

  strng=strng.replace(" ","") #remove spaces

  #now this is the complete string from 0 to n number
  count=0
  num=0
  for i in strng:
    if i==str(num):
      count += 1
  print(count)
func(10)

#Azizullah Ali

- Data Science Engineer

---

您的答案如果加上更多的支持性信息会更好。请编辑以添加进一步的细节，如引用或文档，以便他人可以确认您的答案是正确的。您可以在帮助中心找到有关撰写良好答案的更多信息。 - Roi

Answer 6

class FindZero{

    public int findZero(int lastNumber){

        int count=1,k;
        if(lastNumber<10)
            return 0;
        else if(lastNumber==10)
            return 1;
        else{

            for(int i=11;i<=lastNumber;i++){
                k=i;
                while(k>0){

                    if(k%10==0)
                        count++;
                        k=k/10;
                }
            }
            return count;
        }
    }
    public static void main(String args[]){
        FindZero obj = new FindZero();
        System.out.println(obj.findZero(1234));
    }
}

- Vivek singh

Answer 7

我解决这个问题的方法：

数字可以在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

我在这里遇到了一些问题，但是这个方法可以行得通。

- brainydexter

---

@Nemo：我认为这与你建议的类似。你能帮我将其概括成一个函数吗？ - brainydexter