> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/hard/count-of-25.md).

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/hard/count-of-25.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.