你如何有效地计算从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之间".我们可以通过看到某种模式来做到吗？
我们来定义eleven-non-free数字:
如果我们将数字视为一个字符串,那么如果内部的任何子字符串是(非零)幂11,则该数字是一个eleven-non-free数字.
例如,内部是1123一个eleven-non-free数字.同样是一个为是.但事实并非如此,因为我们无法找到任何内部的非零力量.1111^11215412111^21234511
所以给定ak,找到第k个eleven-non-free数字.例如,第13个这样的数字是211.
我不知道如何有效地做到这一点.蛮力的方法是将i从1增加并检查每个数字和计数直到第k个.
我想我们应该考虑不同长度的字符串(1,2,3,4,...).然后对于每个长度,我们尝试填写11,11 ^ 2,11 ^ 3等,并尝试获得所有组合.
但它似乎也很复杂.
任何人？