给定数字n,找出0 ... n范围内有数字2的数字

Question

这是一个面试问题.

给定数字n,找出0 ... n范围内有数字2的数字

例如 ,

输入= 13输出= 2(2和12)

我给出了通常的O(n ^ 2)解决方案,但有更好的方法.

是否有任何"技巧"公式可以帮助我立即得到答案

Answer 1

计算没有数字2的数字.在小于10 ^k的数字中,恰好有9 ^k.然后它仍然是将数字从10 ^k处理到n,其中

10^k <= n < 10^(k+1)

你可以通过单独处理第一个数字(案例2和其他必须区分),然后前两个数字等来做.

例如,因为n = 2345,我们发现有9^3 = 729数字2没有1000以下的数字.在1000到1999的范围内再有729个这样的数字.然后在2000到2345的范围内,没有,总共1458,因此包含数字2的数字是

2345 - 1458 = 887

如果你用前导零写数字,数字0到'10 ^ k - 1`正好是你可以用'k'数字写的数字.对于每个数字,有9个(`== 10 - 1`)可能的选择(`0,1,3,4,5,6,7,8,9`).选择是独立的,因此选择的总数是每个数字的选择数量的乘积,`9*9*...*9 = 9 ^ k`.如果你的数字既不包含数字2也不包含数字5,那么它将是'8 ^ k`(8 = 10 - 2).同样的原则适用于其他基础中数字的表示.但是,由于数字实际上没有前导零,因此... (4认同)