给定一个数n,找出有多少数字有数字2的范围0,...,N [英] Given a number n, find out how many numbers have digit 2 in the range 0...n
问题描述
这是一个面试问题。
给定一个数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
这篇关于给定一个数n,找出有多少数字有数字2的范围0,...,N的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!