[20.4] Count the number of 2s between 0 and n

1. Example

LeetCode: Number of Digit One

      1,2,3,4,5,6,7,8,9,10,
   11,12,........
20,..,29,
30,...32,39,..
      ..42,.
      ..52,..
       .92,.
    ..102, ,
120,129..
      .192,...
200,...299...

>2   => first digit, with 2X, at least power 52 = 20~29[power =10], 513=200~299[power = 100]  
==2 => first, digit, with 2x, at lest remainder+1 25=[20-25][remainder +1=6], 279=[200-279][reminder +1=80]

all other digit power-1  + reminder
Recursive MSB->LSB, maximum power you got200~299, first digit and remainder, first digit >2 power or ==2 remainder +1 AND first*f(power-1)20~29,22-92 + f(reminder)
513 = 100,5,13
32 = 10,3,2
f(513) =  100 + 5*f(99) + f(13)

           =  100 + 5* 20    + 2 
           = 202

Iterative    LSB->MSB, LSB as first digit power or remainder, remainder for next digit,
digit*pos*power/10[like 5*f(99)] digit*previous count
f(513) = f(3)  3*0*1/10     + [3>2, count+=1]       = 0 + 1 

              f(1)  1*1*10/10   + [1<2, count+=0]       = 1 + 0 

              f(5)  5*2*100/10 + [5>2, count+=100]   = 100 +100

          = 202

// NOTE: accumulate from previous
count+= digit*pos*power/10;

remainder = digit * power + remainder;






f(2) = 1st digit       1  [2]

                al other digit        0
2 = 2* 1 + 0
f(52)     =  1st digit                10  [20,..29]
                al other digit        f(2)
52 = 5* 10 + 2
f(513) =  1st digit           100  [200-299]
                all other digit 5*f(99) + f(13)
513 = 5 *100 + 13
f(279) =  1st digit           80  [200-279]
                all other digit 2*f(99) + f(79)
279 = 2*100 + 79
int nTwoFirst = 0;

if (first > 2 )

 nTwoFrist += power; 

else if (first == 2) 

nTwoFirst += reminder + 1; 

// Count 2s from all other digits

 int nTwoOther = first*count2s(power -1) + count2s(remainder);

f(279) = 2*f(99) + f(79)  + 79+1[200-279] 
2 in the first digit ,in the second digit, in the third digit[the last digit]
There are X2     between 0 and 99   [2,12,32,43,52,62,72,82,92] = > 10 Twos
                2X     between 0 and 99   [ 20,   21,...  29]                    = > 10 Twos
There are 2X     between 0 and 199 [  20,   21,...  29
                                                       120, 121, ..129] => 20 Twos
There are 2XX  between 0 and 299 [ 200,201,.....299 ] => 100 Twos
                                                         [    20,21,,,,29,
                                                             120,  .....129,
                                                             220, ... ...229]  => 30 Twos
  0     1      2 ....  9
  10   11   12     19
  20
  30....
...
110 111          119
The last digit repeat every 10 numbers, 0,10,20,30..
The last two digit repeated every 10^2 numbers, 10, 110, 210,..
The last three digit repeated every 10^3 numbers, 110, 1110,..

  0     1      2 ....  9      => one 2
  10   11   12     19    => one 2
  20                           => one 2 from 2'2'+ ten 2 from 2X
  30....
...
110 111          119  => one 2

210.................219  => one 2 from 12 + ten 2 from 2XX

f(513) = the last digit 2 [2,12,22,32,...512] + the last 2 digit 2X[2x, 12x,22x, ..42x] + the last three digit 2xx[2xx]
          = (512-2)/10+1   +    (420-20)/100+1 + 1
          = 52 + 5 + 1

2. Implementation

public static int count2s(int n)
{




      //validate the input
      // Base Case
      if ( n == 0 )
            return 0;
        
 


       int power =1; 
       while ( 10 * power < n )  power*=10;  // power =100
       int first = n / power ;               // first = 5
       int remainder = n % power;            // remainder = 13




       // Count 2s from the first digit
       int nTwoFirst = 0;
       if (first > 2 ) nTwoFrist += power;
       else if (first == 2) nTwoFirst += reminder + 1;

       
       


       // Count 2s from all other digits
       int nTwoOther = first*count2s(power -1) + count2s(remainder);





       return nTwoFirst + nTwoOther;

 


}

public static int count2s(int n)
{




     
       int count =0;
       int digit = 0;
       int j = num; 
  

       int power     = 1;
       int remainder = 0;
       int pos = 0;

     

       // maintaining this value instead of calling pow() is an 6x 
       // perfgain
       // 513 = 51*10 + 3
       //  51 = 5*10  + 1
       //   5 = 0*10  + 5
       while (  j > 0 )
       {




            digit = j % 10;
            


            // NOTE: accumulate from previous
            count+= digit*pos*power/10;




            // NOTE: Seen it as First digit
            if (digit ==2 )
            {
                 // NOTE: First digit count =  reminder +1 
                 // 250 = 2*100 +50 = [200,..250] => 50+1
                 // 25 = 2*10 + 5= [20,..25]      => 5+1
                 // 2  = 2*1 + 0 = [2]            => 0+1
                 count += remainder +1;                 
            }
            else if ( digit > 2)
            {
                 // NOTE: First digit count =  power 
                 // 500 = 5*100 = [200,..299]
                 // 50 = 5*10= [20,..29]
                 // 5  = 5*1 = [2]            
                 count += power; 
            }

  

            
            j  = j / 10;
            remainder = digit * power + remainder;
            power *= 10; 
            pos ++;


       }





       return countOf2s;





}

3. Similar Ones