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

Question

It's an interview question.

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

For example ,

input = 13 output = 2 (2 and 12)

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

Answer 1

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)

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.

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