计算从1到N的整数的出现次数

您将如何有效地计算从1到N的整数十进制表示中0的出现次数?

eg 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之间”。 我们可以通过看到某种模式来做到吗?

我们不能扩展这里编译的逻辑来解决这个问题吗?

更新的答案

我原来的答案很容易理解,但很难编码。 这里的代码更简单。 这是一个直接的非递归解决方案,通过计算零在每个位置出现的方式来工作。

例如:

x <= 1234.以下表格中有多少个数字?

x = ?? 0?

“数百或更多”(1,2,…,12)有12种可能性。 然后一定是零。 然后最后一位数有10种可能性。 这给出12 * 10 = 120数字,在第三个数字处包含0。

因此,范围(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开始,我们只能在最后两位数字中选择0034之间的数字。 所以我们总共获得了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:

一个范围内整数的二进制补码表示中的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)贡献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); } 

情况n < 10的丑陋再次来自范围为1到n而不是0到n ...对于任何大于或等于d的单位数n ,除非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都在该范围内,每个最后十个digit为0,所以k为零,每个前缀j (除了最后一个数字之外)都出现十次,但是我们不能计数0,所以前缀中的零数是10*(Z(k)-1)

r10*k, ..., 10*k + (r-1)r*number of zeros in k + (r > 0 ? 1 : 0)

所以我们有一个用于计算Z(n)O(log 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 } 

我解决这个问题的方式:

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

我从这里开始遇到一些麻烦,但这会奏效。

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