这是一个面试问题。

给定一个数n，找出有多少数字有数字2在0 ... N

Given a number n, find out how many numbers have digit 2 in the range 0...n

例如，

输入= 13输出= 2（2-12）

input = 13 output = 2 (2 and 12)

我把平时为O（n ^ 2）解决方案，但有没有更好的办法。

I gave the usual O(n^2) solution but is there a better approach.

有什么绝招的公式，这将有助于我得到的答案的时候了。

is there any 'trick' formula that will help me to get the answer right away

推荐答案

计数做数字的不可以有数字2。在数字不到10 K ，恰好有9 K 他们。然后，它仍然从10对待号 K 到 N ，其中

Count the numbers that do not have the digit 2. Among the numbers less than 10k, there are exactly 9k of them. Then it remains to treat the numbers from 10k to n, where

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

而可以通过单独处理第一数字（例2和其他必须加以区别）做的，那么第2位数字等

which you can do by treating the first digits individually (the cases 2 and others have to be differentiated), and then the first 2 digits etc.

例如，对于 N = 2345 ，我们发现有 9 ^ 3 = 729 数字没有数字2以下1000有再次729这样的数字范围从1000到1999年。然后，在从2000年至2345的范围内，有无，共计1458，因此含有该数字2的数字是

For example, for n = 2345, we find there are 9^3 = 729 numbers without the digit 2 below 1000. There are again 729 such numbers in the range from 1000 to 1999. Then in the range from 2000 to 2345, there are none, for a total of 1458, hence the numbers containing the digit 2 are

2345 - 1458 = 887