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.