Count the number of 2s between 0 and n

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⋅10^m. 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 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⁰=1,
N((0,100])=2×10¹=20,
N((0,1000])=3×10²=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.

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∗10^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

• http://tianrunhe.wordpress.com/2012/06/04/count-the-number-of-2s-between-0-and-n/
• http://www.delbertbao.net/2012/07/01/counting-2s/