Naboo

Wednesday, April 20, 2011

A Different Thinking Process for "Count the number of two's from 1 to n"

Careercup-150 solves this problem by this approach:
Pattern: 0-10: 1 2s; 0-100: 20 2s; 0-1000: 300 2s; between 0 and 10^n, there are n*(10^n-1) 2s. Let f(n)=n*(10^n-1), we have: between 0 and x*10^n, number of 2s becomes:
  • x>2  -- x*f(n) + 10^(n-1)
  • x=2  -- x*f(n) + 1
  • x<2 -- f(n-1)
For 2145, we have to consider these 4 intervals: 1-2000, 2000-2099, 2100-2139, 2140-2145. Pattern solves counting in intervals starting from 0 or 1, I am too dumb to see how this split is going to use the pattern. Surprisingly, code in the book seems to be exactly same as mine, which indicates that my thinking process should be correct. Hence the elaboration below:

Think of the problem as your car pedometer, the numbers roll up, over and push the next column. Patter: every 10 miles, the digit for 2 rolls once; Every 100 miles, the 10's digit rolls 2 10 times; Every 1000, the 3rd digit rolls 2 100 times. Take the number 2145, starting from 5 as p0 slot, we have p3p2p1p0 four slots. Number of 2's occurred for each slot would be:
  • p0: (214+1)*1   //pedometer slot 0 was rolled from 0-9 214 times, plus 1 to reach 5
  • p1: (21+1)*10  //pedometer slot 1 was in 2 position for 22 times, which includes rolling 0-9 for 21 times, and 1 time before it reaches 4
  • p2: 2*100        //pedometer slot 2 was rolled from 0-9 2 times, i.e., 200-299, and 1200-1299.
  • p3: 146            //bcoz p3=2 and p3 is the highest slot, this slot has stayed at 2 from 2000 for 146 times.
In a nutshell: First look at left slot to calculate how many "full roll" current has gone through, multiple it by 10^(slotPosition-1). Then, depending on whether current slot is <2, 2 or >2, do corresponding calculation.

Code(shorter than Careercup hooray!)
public static int CountTow(int n) {       
        int sum = 0;
        int temp = n;
        int base = 1;
        while(temp>10) {           
            sum += base * temp/10 + (temp%10>1? 1:0);
            temp = temp/10;
            base*=10;
        }
        if (temp==2) {
            sum += (n-2*base+1);
        }else if(temp >2) {
            sum += base;
        }
        return sum;
    }

Unitest
CountTow(-1)   - 0
CountTow(0)    - 0
CountTow(1)    - 0
CountTow(2)    - 1
CountTow(12)  - 2
CountTow(20)  - 3
CountTow(29)  - 13
CountTow(100) -20
CountTow(1000)  -300
CountTow(2145)   -786

0 Comments:

Post a Comment

<< Home