# [CC150v4] 20.4 Count 2s in Digits

### 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));