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

**My initial thoughts:**

We need recursion. For a number, we split it into two parts: the MSB and the reminder. For example, 319 has MSB of 3 and reminder of 19.

- Count the number of 2s for MSB:
- If MSB > 2: We will have 1 or 10 or 100 or 1000, etc 2s. In this case of 319, we have 100 2s (occurring at MSB from 200 to 299).
- If MSB == 2: We will have reminder+1 2s. For example if we have n = 219, we have 20 2s (occurring at MSB from 200 to 219).

- Count the number of 2s for reminder, two parts:
- Recursively count the number of 2s for the tens. For example of n = 319, we’d like to recursively count number of 2s from 1 to 100. We then know we have 3 times that number of 2s. This is like: we know number 12 has a 2, so we know number 12, 112 and 212 have three 2s.
- Count the number of 2s causing from the reminder. For example of n = 319, we’d like to recursively count number of 2s from 1 to 19. That counts for the number of 2s appearing from 301 to 319.

**My initial codes:**

// Take n = 319 as example
public static int numberOf2s(int n) {
if (n < 2)
return 0;
int result = 0;
int power10 = 1;
while (power10 * 10 < n) {
power10 *= 10;
}
// power10 = 100
int msb = n / power10; // 3
int reminder = n % power10; // 19
// Count # of 2s from MSB
if (msb > 2)
// This counts the first 2 from 200 to 299
result += power10;
if (msb == 2)
// If n = 219, this counts the first 2
// from 200 to 219 (20 of 2s).
result += reminder + 1;
// Count # of 2s from reminder
// This (recursively) counts for # of 2s from 1 to 100
// msb = 3, so we need to multiply by that.
result += msb * numberOf2s(power10);
// This (recursively) counts for # of 2s from 1 to reminder
result += numberOf2s(reminder);
return result;
}

### Like this:

Like Loading...

*Related*

tommyHU

Mar 18, 2014@ 16:04:32Nice solution. 🙂

P.S.: I referred your code and generalize to count Ks here: http://stackoverflow.com/q/20945790/2589776