How many times "2" occurs in all numbers from 0 to n

Question

find how many times "2" occurs in all numbers from 0 to n .

example : n= 112 answer = 22

numbers : 2 , 12 , 20-29 , 32 ...  92 , 102 ,  112  

I came up with the following method :

let k= number of digits of n

f(k) = number of two's from 0 to 10^k-1 ..

f(1) = 1 // 2
f(2) = 10*f(1)+ 10^(2-1) // 12 , 20 - 29 , 32 ... 92
f(3) = 10*f(2)+ 10^(3-1)
and so on ...

twos(int n , int k)
{
    if(n<2)
        return 0;
    else if(n<10)
        return 1;

    msb = n/10^k
    remainder = n%10^k

    if(msb==2) // eg 230 ,  calculate 200 ... to 230  , and find twos from 0 on 199  and recursion on 30
        return msb*(f(k)) + (remainder+1) + twos(remainder) // 2*(below 100) + 31 + tows(30)
    else if (msb>=3)
         return msb*(f(k)) + (10^k) + twos(remainder)  // for 312 -> 3*(below 100) + 100 + twos(12)
    else
        return  msb*(f(k)) + twos(remainder)

}  

Is my approach correct ?
If so , is there any solution faster than this ?

EDIT :
My approach seems correct for these test cases , here is simulation
results :
1st coloumn : n , 2nd coloumn : brute force , 3rd coloumn : my method

2 1 1
5 1 1
91 19 19
868 277 277
7783 3359 3359
55576 32718 32718
293911 242093 242093
10179297 7091858 7091858
59939789 51975959 51975959

Answer 1

Let's say the number consists of digits n=... n4 n3 n2 n1. We want to look at all numbers x<=n and count the digits 2 within them. x shall be represented as x=... x4 x3 x2 x1. As a start, we count how many numbers have a 2 as last digit, x1==2:

f1(n) = (n+8) / 10

assuming the division truncates. Some examples:

f1(1) = 0
f1(2) = 1
f1(12) = 2
f1(21) = 2
f1(22) = 3 

Now let's count the numbers that have a 2 as second to last digit, x2==2. This is similar to cutting of the last digit of n and then counting the numbers that have a two as last digit:

f2(n) = 10 * f1(n/10)  # almost right

Let's test it:

f2(10) = 0
f2(20) = 10 * f1(2) = 10  # wrong
f2(25) = 10 * f1(2) = 10  # wrong
f2(29) = 10 * f1(2) = 10  
f2(30) = 10 * f1(3) = 10

We need special handling for the case when the second to last digit of n is a two itself, n2==2:

f2(n) = 10*f1(n/10) - 9 + n1 # if n2==2

With n1 == n % 10 (remainder function) this can be written as:

f2(n) = 10*f1(n/10) - 9 + n%10 # if n2==2

Similarly for counting the numbers where x3==2:

f3(n) = 100*f1(n/100) # if n3 != 2
f3(n) = 100*f1(n/100) - 99 + n%100 # if n3 == 2

Summing it all up we get for the total number of 2's:

f(n) = f1(n) + f2(n) + f3(n) + ...

In Java:

public static int count2(int n) {
    int res = (n+8) / 10;
    int divider = 10;
    while (n>= 2*divider){
        int na = n / divider;
        res = res + divider * ((na+8) /10);
        if (na%10==2)
             res = res - divider + 1 + n % divider;
        divider = divider * 10;
    }
    return res;
}

Answer 2

Let f(k) be the number of appearances of the digit 2 in numbers from 0 to 10^k-1 (i.e. up to k-digit numbers). Note that when increasing the digits from k-1 to k, we have f(k-1) appearances for every one of the new leading digit, plus 10^(k-1) appearances in the leading digit itself:

f(k) = 10*f(k-1) + 10^(k-1)

(Which is exactly your formula)

Solving this recurrence gives:

f(k) = k * 10^(k-1)

For example:

f(1) = 1
f(2) = 20
f(3) = 300
f(4) = 4000
...

There's actually a different way to get this formula. Consider all k-digit numbers (where missing leading digits are replaced with zeroes). The number of numbers is 10^k, and we have k digits in each, therefore we have a total of k*10^k digits. Now, every possible digit appears the same number of times, which is k*10^k / 10 = k*10^(k-1).

-- EDIT --

The following Java solution uses the formula above, and solves the problem for an arbitrary n in O(log n) time:

// Counts occurrences of digit 2 in numbers less than n
public static int count(int n) {
  int count = 0;
  int factor = 1;
  int pos = 0;
  while (true) {
    int m = n / factor;
    if (m == 0) //Past last digit
      break;
    int d = m % 10;      

    count += d * pos * factor / 10; 

    if (d == 2)
      count += n % factor;
    else if (d > 2) {
      count += factor; 
    }

    factor = 10 * factor;
    pos++;
  }

  return count;
}