c - 如何计算范围号 1 到 n 中 0 或 1 的总出现次数？

Question

所以，我想找出一个数字范围内出现了多少个数字0或1。例如:我想找出从数字1到100中出现了多少个0。答案是，0出现了11次。我想将其实现到C，但我不知道该怎么做。

所以，我想要的第一件事是接收一个输入类型int(假设int是n)。然后，从数字1到n，这些范围内出现了多少个0，以及这些范围内出现了多少个1。然后打印出现了多少个0和出现了多少个1的总数。

这是我尝试过的，但尚未完成。

#include <stdio.h>

int main()
{
    int N, totalZero = 0;

    scanf("%d", &N);
    for (int i=N; i>0; i--)
    {
        //statement
    }
    return 0;
}

我不知道在 for 中的//语句中必须做什么。

Answer 1

该问题可以通过数学方式解决，而无需迭代范围内的每个数字并计算其位数。它的工作原理是计算特定数字在每个位置出现的次数。

示例

让我们以计算 1 中 7 的数量为例。至3876 .

每个地方出现7的次数

• 1位:(0)7, 17, 27, ..., 107,...3867 =387 x1次
• 10位: (0)70, 71, 72, 73,..., 79, 170,..., 179,...3770, ..., 3779 =38 X 10 = 380 和 3870, ..., 3876 之间:7 倍，等于 387 .
• 百位:700, ... 799, ..., 3700, ... 3799 =(3 + 1) x100 =400
• 千位:0次。

总计 = 387 + 387 + 400 =1174这就是想要的结果。

代码

我们定义cntdigit(N, digit)作为返回 digit 次数的函数如果从 1 开始计数，则会出现至N .

long long cntdigit(long long n, int digit)
{
  long long j;
  long long res = 0;
  for(j = 1; n/j; j *= 10) {
    long long curdigit = (n / j) % 10;
    res += (n / j / 10) * j;
    if (curdigit > digit)
      res += j;
    else if (curdigit == digit)
      res += n % j + 1;

    if (digit == 0)
      res -= j;
  }
  return res;
}

时间复杂度:

对于 O(d) 中的任意数字都可以解决该问题时间复杂度其中 d是基数 10 的位数对于 n .

说明:

1. 迭代数字 n 的所有数字将其除以 10 的指数和模组10获取每个数字。 (请参阅 this 了解更多详情)。
2. 然后我们开始在每个地方计数，次数digit发生。
3. 在每个位置，左边部分(即除以 10 的指数时得到的商)是数字在个位、十位、百位等中出现的次数。
4. 如果当前数字大于digit然后我们添加j (10 秒指数)用于计算从 0 开始的所有商。
5. 如果当前数字等于 digit那么该数字在该位置出现的次数就是指数 + 1 的余数。
6. 最后，如果要统计的数字是 0 ，那么我们需要减去商 0 的次数。 为什么？因为我们不想对以 0 开头的数字进行 0 计数。例如，您不想计算数字中的 0、01、02、03 等。

该解决方案可以轻松扩展以在范围 a 之间进行计数至b减去 b 的解和a - 1 :

int main()
{
  long long a, b;
  // Range and digit
  scanf("%lld %lld", &a, &b, &digit);
  printf("%lld ", cntdigit(b, i) - cntdigit(a-1, i));
  return 0;
}

如果您有兴趣，可以在SPOJ测试此问题的一般情况的解决方案。