编写一个算法来查找F(n)设置为1的位数,对于任何给定的n值,从1到n的所有数字.
复杂性应该是 O(log n)
例如:
1: 001
2: 010
3: 011
4: 100
5: 101
6: 110
所以
F(1) = 1,
F(2) = F(1) + 1 = 2,
F(3) = F(2) + 2 = 4,
F(4) = F(3) + 1 = 5,
etc.
我只能设计一种O(n)算法.
你如何有效地计算从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之间".我们可以通过看到某种模式来做到吗？