Saturday, July 16, 2011

Calculate the Occurrence of "2" from 1 to N

Problem: Given an integer N, calculate the occurrence of digit "2 " in all the numbers from 1 to N. For example, if N=24, then the integers that have digit "2" are 2, 12, 20, 21, 22, 23 and 24. So totally eight "2"s ( "22" contains two "2"s).

Solution: It is a straightforward solution, Just inspect each digit starting from the tail. For each digit, we need to think of three cases: >2, =2 and <2. The code is listed as follow:

int calculte_2(int input)
{
     int cnt = 0;
     int base = 10;
     int quotient,remainder;

     do
     {
        quotient= input/base;
        remainder = (input%base) / (base/10);
        
        if(remainder>2) cnt += (quotient+1)*base/10;
        else if(remainder<2) cnt +=  quotient*base/10;
        else if(remainder==2) cnt +=  quotient*base/10 + (input%(base/10)) + 1;               
        base*=10;
           
     }while(quotient>0);
     
     return cnt;     

}

No comments:

Post a Comment