### Question

Write a method to count the number of 2s between 0 and n.

### Solution

**This is a difficult question**, especially hard to come up with the correct formula. Eg.

f(279) = {(79 + 1) + 2 * f(99)} + f(79)

f(513) = {100 + 5 * f(99)} + f(13)

Take 513 as example, the first digit is 5. We know that all the 200+ is within the range, so **there’re 100 twos in the first digit**. Then, for the rest of the digits, we get f(99) for number between 0 and 99, and another f(99) for number between 100 and 199… and **this happens 5 times until 499**. That’s why we have 5 multiple by f(99).

In the end, we do the calculation **recursively for reminder number 13**.

### Code

```
public static int myAnswer(int n) {
if (n == 0)
return 0;
int power = 1;
while (power * 10 <= n) {
power *= 10;
}
int first = n / power;
int reminder = n % power;
int firstDigit2count = 0;
if (first > 2) {
firstDigit2count = power;
} else if (first == 2) {
firstDigit2count = reminder + 1;
}
int totalCountBeforeReminder = firstDigit2count
+ (first * myAnswer(power - 1));
return totalCountBeforeReminder + myAnswer(reminder);
}
```