### 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**, 1

**2**,

**2**0))

### 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⋅10

^{m}. Example for numbers

**2**00 to

**2**99, 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 10^{m}.

- 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×10

^{0}=1,

N((0,100])=2×10

^{1}=20,

N((0,1000])=3×10

^{2}=300,⋯

N((0,10

^{x}=x×10

^{x−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.

- 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.

^{m}). 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**

## 0 comments:

## Post a Comment