Count All 2s between 0 to n

Related: LeetCode 233 - Number of Digit One
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;
 }

 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;
 }

https://tianrunhe.wordpress.com/2012/06/04/count-the-number-of-2s-between-0-and-n/

We need recursion. 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.

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;

}