# Let's solve one problem from codeforces today. (problemset/problem/1766/A)

## Problem Statement:

It is a question of 800 rating on CF, if you have not tried it go and try 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.

```
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.

```
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:

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

`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.

```
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:

```
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:

- 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.

```
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 for more.