# Count of 25

**17.6 Count of 25:**Write a method to count the number of 2s that appear in all the numbers between 0 and n (inclusive).

EXAMPLE Input: 25

Output: 9 (2, 12,20, 21,22, 23,24 and 25. Note that 22 counts for two 2s.)

- We have 1 '2' significant digits in the base, with 1 special case. If the number itself exceeds 20, then it is an addition 1 x 10 + 1 = or 11 2's. An additional base would be mean 2 x 10 + 1 = 21, and so fourth.
- Computationally, that means looking to see how many times we can subtract by 10 before the number becomes less than zero. Every -10, gives us one 2. Every -100 gives is a bonus 10 x 1, every -1000 gives us a bonus 10 x 2, and so on. Even faster, I can just see how many times I can divide by 10, and then just see how many times I can divide that number. This property has a name... logarithm (log base 10). Then, all that I have to do from there is just take the number I initially divided by 10, and manually count the 2s until I finally reach the number. This will be very fast, because I can determine most of the 2's mathematically, and will at most have count 10 things at most.

num | num 2's |

10 | 1 + 10 x 0 |

100 | 10 + 10 x 1 |

1000 | 100 + 10 x 2 |

10000 | 1000 + 10 x 3 |

$floor(num/10) + floor(log_{10}(num/10))$

int num2s(long int num) {

const int adder = floor(num / 10);

const int multiplier = floor(log10(adder));

int total = adder + (10 * multiplier);

string remain_str;

int remain_int = adder * 10;

for (int i = remain_int; i <= num; i++) {

remain_str = to_string(i);

for (auto j : remain_str) {

if (j == '2') {

total++;

}

}

}

return total;

}

int main()

{

cout << num2s(100) << endl;

cout << num2s(1000) << endl;

cout << num2s(10000) << endl;

cout << num2s(100000) << endl;

cout << num2s(789) << endl;

cout << num2s(85789378) << endl;

}

Last modified 4yr ago