Wednesday, March 18, 2015

Number of twos between 0 to n

If we partition the array based on the digits, given 2354, we will have:
2 3 5 4

In each 100 to 999, we will have X 2s, so 2000 will give us 2 * X 2s. In 2000, we will have another 355 2s because of the 4th digit from 2000 to 2354, and the rest comes from 354. So the function looks like:

2 * numTwos(999) + numTwos(354) + 354 + 1

What if we have 3354 instead of 2354?
Now from 2000 to 2999, we will have 1000 2s. So the function becomes:

3 * numTwos(999) + numTwos(354) + 1000

Yep, a simple recursive solution would help.


public static int numTwos(int n){
  if(n < 2)
   return 0;
  if(n < 10)
   return 1;
  int power = 1;
  while(10 * power <= n) power *= 10;
  int first = n / power;
  int reminder = n % power;
  int firstPart = 0;
  if(first > 2)
   firstPart += power;
  else if (first == 2)
   firstPart += reminder + 1;
  int secondPart = first * numTwos(power - 1) + numTwos(reminder);
  return firstPart + secondPart;
  
 }

No comments:

Post a Comment