Let's solve one problem from codeforces today. (problemset/problem/1766/A)
Published: 2024-05-12 05:31:37

## Problem Statement:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4e7dp6dtv9hxxufl2quc.png)


It is a question of 800 rating on CF, if you have not tried it go and try [problemset/problem/1766/A](https://codeforces.com/problemset/problem/1766/A first).

## Let's discuss the solution now:

> a positive integer extremely round if it has only one non-zero digit. For example, 50005000, 44, 11, 1010, 200200 are extremely round integers; 4242, 1313, 666666, 7777, 101101 are not.

so let's define a function which will take a integer n as an input and return is it a extremely round integer or not.

```python
def is_round(n):
    digits = list(map(int, str(n)))
    return digits.count(0) == (len(str(n)) - 1)
```
Now the idea is for each test case t we will iterate and find the number of extremely round integer for it.
```python
def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        count_of_round = 0
        for i in range(n+1):
            if is_round(i):
                count_of_round += 1
        print(count_of_round)

main()
```
but the problem is:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/d28cscomqp1y067cno6f.png)


### Let's go through the PS once again:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/smwycyxkvc0ltl6twy6d.png)


`n(1<=n<=999999)` let's take the advantage of this limit:
We already know `n` can't go beyond `999999`. and we are calculating the number of extremely round integers from 0 to n for each number n. let's memorize this answers. I will take a array named `dp` and store `answers(k)` from `0 to 999999` in the dp array. when a new n comes we will access the specific index and return the specific answer.

```python
dp = [0]
    for i in range(1, 999999+1):
        if is_round(i):
            dp.append(dp[len(dp)-1] + 1)
        else:
            dp.append(dp[len(dp)-1])
```

### Let's write the complete code:
```python
def is_round(n):
    digits = list(map(int, str(n)))
    return digits.count(0) == (len(str(n)) - 1)

def main():
    dp = [0]
    for i in range(1, 999999+1):
        if is_round(i):
            dp.append(dp[len(dp)-1] + 1)
        else:
            dp.append(dp[len(dp)-1])

    t = int(input())
    for _ in range(t):
        n = int(input())
        print(dp[n])

main()
```
### result:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uew2y1ikl1e742eozm79.png)


- Time Complexity of each test case = O(10⁷)
- Space Complexity of each test case = O(10⁷)
- Time Complexity = O(t*10⁷)
- Space Complexity = O(t*10⁷)

But we can still do better, Intuition: every interval of (n+1) and (n)*10 have exactly 9 extremely round.

> For example: 11 to 100 have exactly 9 extremely round integer - 20, 30, 40, 50,60 70, 80, 90, 100.

And every interval of ((i*10)+1) and ((i+10)*10) have exactly 1 extremely round integer.

> Example: 201 to 300 we have only one extremely round integer - 300.

```python
def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        m = 1
        ans = 0
        while m*10<n:
            ans += 9
            m *= 10

        ans += n//m
        print(ans)

main()
```

- Time Complexity of each test case = O(log(n, base=10))
- Space Complexity of each test case = O(1)
- Time Complexity = O(t*log(n, base=10))
- Space Complexity = O(1)

[Follow](https://www.linkedin.com/in/swarnendu-bhandari-847590290/) for more.