给定一个数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 10^k, there are exactly 9^k of them. Then it remains to treat the numbers from 10^k 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屋！