Categories
Mastering Development

How to determine how many times ‘0’ to ‘9’ have been used in a specific range having O(N) Time complexity?

I want to count how many times ‘0’ to ‘9’ have been used in a specific range

e.g. 112 has two ‘1’ and one ‘2’

I wrote this code, but it has O(n^2) Time complexity.

num = int(input('n : '))
arr = [0] * 10

for i in range(1, num + 1):
    for j in range(10):
        arr[j] += str(i).count(str(j))

print(arr)

When I input 1000 as n, my program will print this arr instantly

[192, 301, 300, 300, 300, 300, 300, 300, 300, 300]

It means for 1 to 1000,
‘0’ has been used 192 times and ‘1’ has been used 301 times and ···

But when I input 2,000,000,000 as n, my program will print the result after
I am dead XD.

So I want to change my code having O(N) Time complexity to get the result of ‘n : 2 billion’

I think there is a specific rule, but I can’t find it T.T

Leave a Reply

Your email address will not be published. Required fields are marked *