## Tuesday, July 22, 2014

### Problem

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

### Example

Input Range : between 0-20,
Output : 3 (i.e 2, 12 , 20))

### Solution

We need recursion. The number n can be broken down into a couple of ranges. The number of 2’s of numbers in each range is independent of each other. For example, 3345 can be broken into [0, 3000] and (3000, 3345]. We can easily get the formula for the number of 2’s of k⋅10m. Example for numbers 200 to 299, we will have 100 2's.

For the extra at the tail, we observe that n2(3000,3345]=n2(0,345]. (0, 345] can then be broken down in the same way. The only catch is, say,  if the range is (2000, 2345], we need to add 345 more 2’s, i.e., n2(2000,2345]=n2(0,345]+345. In general, the total number of added tail is the number of 2’s at the higher bits.

### Algorithm

We need to first count 2’s in the range between 0 and 10m.
• For the lowest digit, 1 out of every 10 numbers has a 2.
• For the 10’s digit, 10 out of every 100 numbers have a 2.
• In general, for a digit x, 1 out of every 10 numbers will have a 2. So the total number of 2’s depends on how many digits we have. Define the number of 2’s in the range X as N(X). We have

N((0,10])=1×100=1,
N((0,100])=2×101=20,
N((0,1000])=3×102=300,⋯
N((0,10x=x×10x−1

for k =1 no extra 2 in leading digit, for k=2, it’s one extra 2, for k>2, there are 10x leading 2s.
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.
1. Count the number of 2s for MSB:
1. 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).
2. 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).
2. Count the number of 2s for reminder, two parts:
1. 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.
2. 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.
Process from low to high, accumulate counts in each step with N(0,digit∗10m). In processing from low to high, we can also keep track of the number to the right so that when we encounter a digit>=2, we can add the number to the right to the count.

```// 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;
}
```

Reference