## Friday, July 8, 2016

### 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));//??
}
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;
}