# 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))$$

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