Count of 2s

http://www.hawstein.com/posts/20.4.html

Write a method to count the number of 2s between 0 and n.

http://www.shuati123.com/blog/2014/09/10/count-2s-in-digits/

This is a difficult question, especially hard to come up with the correct formula. Eg.

f(279) = {(79 + 1) + 2 * f(99)} + f(79)

f(513) = {100 + 5 * f(99)} + f(13)

Take 513 as example, the first digit is 5. We know that all the 200+ is within the range, sothere’re 100 twos in the first digit. Then, for the rest of the digits, we get f(99) for number between 0 and 99, and another f(99) for number between 100 and 199… and this happens 5 times until 499. That’s why we have 5 multiple by f(99).

In the end, we do the calculation recursively for reminder number 13.

public static int myAnswer(int n) {
    if (n == 0)
        return 0;
    int power = 1;
    while (power * 10 <= n) {
        power *= 10;
    }

    int first = n / power;
    int reminder = n % power;
    int firstDigit2count = 0;
    if (first > 2) {
        firstDigit2count = power;
    } else if (first == 2) {
        firstDigit2count = reminder + 1;
    }
    int totalCountBeforeReminder = firstDigit2count
            + (first * myAnswer(power - 1));//??
    return totalCountBeforeReminder + myAnswer(reminder);
}

http://weihungcrackingcodehard.blogspot.com/2015/10/204-count-number-of-2s-between-0-and-n.html
      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; 

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;

}

https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2017.%20Hard/Q17_06_Count_of_2s/Question.java
public static int count2sInRangeAtDigit(int number, int d) {
int powerOf10 = (int) Math.pow(10, d);
int nextPowerOf10 = powerOf10 * 10;
int right = number % powerOf10;

int roundDown = number - number % nextPowerOf10;
int roundUp = roundDown + nextPowerOf10;

int digit = (number / powerOf10) % 10;
if (digit < 2) { // if the digit in spot digit is
return roundDown / 10;
} else if (digit == 2) {
return roundDown / 10 + right + 1;
} else {
return roundUp / 10;
}
}

public static int count2sInRange(int number) {
int count = 0;
int len = String.valueOf(number).length();
for (int digit = 0; digit < len; digit++) {
count += count2sInRangeAtDigit(number, digit);
}
return count;
}

public static int count2sR(int n) {
/* Alternate, messier, solution */

// Example: n = 513

// Base case
if (n == 0) {
return 0;
}

// Split apart 513 into 5 * 100 + 13.
// [Power = 100; First = 5; Remainder = 13]
int power = 1;
while (10 * power < n) {
power *= 10;
}
int first = n / power;
int remainder = n % power;

// Counts 2s from first digit
int nTwosFirst = 0;
if (first > 2) {
nTwosFirst += power;
} else if (first == 2) {
nTwosFirst += remainder + 1;
}

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

return nTwosFirst + nTwosOther;
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2017.%20Hard/Q17_06_Count_of_2s/QuestionBrute.java

public static int numberOf2s(int n) {

  int count = 0;

  while (n > 0) {

    if (n % 10 == 2) {

      count++;

    }

    n = n / 10;

  }

  return count;

}

public static int numberOf2sInRange(int n) {

  int count = 0;

  for (int i = 2; i <= n; i++) { // Might as well start at 2

    count += numberOf2s(i);

  }

  return count;

}