How to determine how many times '0' to '9' have been used in a specific range instantly

To solve this problem efficiently, you can't go through numbers one by one and count up their digits. You need to apply math.

Suppose the upper limit of the range is 123456. Let's try to figure out how many times each possible digit occurs in this range, in the hundreds place.

For every 1000 consecutive integers, each possible digit occurs 100 times in the hundreds place, except for when that digit would be a leading zero. There are 123456//1000=123 full 1000-integer chunks, with 123456%1000=456 integers from 123001 to 123456 left over. The full chunks give us 123*100=12300 occurrences of each digit in the hundreds place, minus 99 for digit 0 because of leading zeros.

In the range from 123001 to 123456, 0 appears 99 times in the hundreds place, each digit from 1 to 3 appears 100 times, and 4 appears 57 times.

Figure out how to formalize this logic enough to implement it in a program, and apply it to every digit place, and you'll easily be able to handle inputs much larger than 2 billion.

Well, I have a way that will take about 30-40 minutes for an input of 2,000,000,000, is that fast enough? Hopefully that's long before you are dead! It processes about 1,000,000 numbers per second on my machine. The key is that you are calling count() 10 times on each number, once for each digit. But if you just went through the number once and incremented based on what digit you see at each position, then you just run through each number once. My method also doesn't keep much in memory, so it won't run out of space (I chose to use a dict instead of a list of digits, but it should be about the same). My code:

num = 2 * (10**9) # 2 billion
num_dict = {}
for i in range(10):       # Dict to keep track of counts
    num_dict[str(i)] = 0

for i in range(1, num + 1):
    if i%1000000 == 0:           # print progress every Million
        print(f'Processed {i/1000000}M numbers')
    for digit in str(i):
        num_dict[digit] += 1

>>> print(num_dict)
{
    '0': 1688888898,
    '1': 2800000000,
    '2': 1800000001,
    '3': 1800000000,
    '4': 1800000000,
    '5': 1800000000,
    '6': 1800000000,
    '7': 1800000000,
    '8': 1800000000,
    '9': 1800000000
}

I'll update with the answer in 40 minutes if you want
Answer for n : 2billion is above! ;D

Happy Coding!

Ok, I gave it a go at being even s-m-r-t'er. I took a look at the counts at a bunch of powers of 10:

At 10 totaldigits=11, counts are: [1, 2, 1, 1, 1, 1, 1, 1, 1, 1]
At 100 totaldigits=192, counts are: [11, 21, 20, 20, 20, 20, 20, 20, 20, 20]
At 1000 totaldigits=2893, counts are: [192, 301, 300, 300, 300, 300, 300, 300, 300, 300]
At 10000 totaldigits=38894, counts are: [2893, 4001, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000]
At 100000 totaldigits=488895, counts are: [38894, 50001, 50000, 50000, 50000, 50000, 50000, 50000, 50000, 50000]
At 1000000 totaldigits=5888896, counts are: [488895, 600001, 600000, 600000, 600000, 600000, 600000, 600000, 600000, 600000]
At 10000000 totaldigits=68888897, counts are: [5888896, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000]

A pattern has started to emerge! After 10^n numbers, the counts for 2,3,...,9 are equal to n * 10^(n-1), and the counts for 1 are 1 more than that, n * 10^(n-1) + 1. The counts for 0 are less than the others, and appear to be equal to the total digits at the previous power of ten! So, we can count the digits in the numbers through 10, and then for every power after that, the counts for 1 thru 9 can be computed directly, and the counts for 0 can be obtained from the previous total counts. i.e.:

total_digits_in = {}
total_digits_in[10] = 11
highest_power = 9
for cur_power in range(2, highest_power+1):
    counts = [
        total_digits_in[10**(cur_power-1)],     # zero = total counts at previous power of 10
        cur_power * (10**(cur_power - 1)) + 1,  # one = n * 10^(n-1) + 1
        cur_power * (10 ** (cur_power - 1)) ,   # 2 thru 9 = n * 10^(n-1)
        cur_power * (10 ** (cur_power - 1)),
        cur_power * (10 ** (cur_power - 1)),
        cur_power * (10 ** (cur_power - 1)),
        cur_power * (10 ** (cur_power - 1)),
        cur_power * (10 ** (cur_power - 1)),
        cur_power * (10 ** (cur_power - 1)),
        cur_power * (10 ** (cur_power - 1)),
    ]
    total_digits_in[10**cur_power] = sum(counts)
    print(f'Counts for 10^{cur_power}: {counts}')

Counts for 10^2: [11, 21, 20, 20, 20, 20, 20, 20, 20, 20]
Counts for 10^3: [192, 301, 300, 300, 300, 300, 300, 300, 300, 300]
Counts for 10^4: [2893, 4001, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000]
Counts for 10^5: [38894, 50001, 50000, 50000, 50000, 50000, 50000, 50000, 50000, 50000]
Counts for 10^6: [488895, 600001, 600000, 600000, 600000, 600000, 600000, 600000, 600000, 600000]
Counts for 10^7: [5888896, 7000001, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000, 7000000]
Counts for 10^8: [68888897, 80000001, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000]
Counts for 10^9: [788888898, 900000001, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000]

This gets you the exact counts of each digit if going through the integers from 1 through a power of 10, essentially instantly. I think it will be significantly harder to get the counts for an arbitrary number between powers of 10. I don't think it's impossible, just ... difficult. Anyhow, hope you like this new solution!

Use collections.Counter to count the occurrence of digits in each number in the range. And by maintaining the count as you loop through the range, you do it in one pass.

def digits(number):
    c = Counter()
    for n in range(1, number+1):
        c.update(str(n))

    # return [c[str(k)] for k in range(10)]
    return c

Output:

>>> digits(1000)
Counter({'1': 301, '2': 300, '3': 300, '4': 300, '5': 300, '6': 300, '7': 300, '8': 300, '9': 300, '0': 192})

And if you want it as a list of the digits counts from 0 to 9, then change the return line to:

return [c[str(k)] for k in range(10)]

>>> digits(1000)
[192, 301, 300, 300, 300, 300, 300, 300, 300, 300]

As for complexity:

In [8]: %timeit digits(10)
16.8 µs ± 151 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [9]: %timeit digits(100)
113 µs ± 1.22 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [10]: %timeit digits(1000)
1.14 ms ± 8.92 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

For a 10x increase in the input value, there's a 10x increase in the time taken. That's O(n), not O(n^2).

If you're defining "n" not as the input number but as the length of the input number (number of digits), then yes, it's O(n^2). But that's an arbitrary decision on what "n" is. By that metric, all numerical algorithms which are currently O(n) would immediately become O(n^2). (I suppose defining the basis of 'n' is flexible.)

Here's a slightly version faster version of the same function, though having the same time complexity:

def digits(number):
    c = Counter(char for n in range(1, number+1) for char in str(n))
    return c  # or as one line

In [19]: %timeit digits(10)
7.15 µs ± 231 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [20]: %timeit digits(100)
47.5 µs ± 1.81 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [21]: %timeit digits(1000)
606 µs ± 48.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Finally I did it!

def main():
    n = int(input('n : '))
    num_arr = [0] * 10
    w = 1

    for step in range(len(str(n))):
        remaining = 9 - int(str(n)[-1:])

        for i in range(len(num_arr)):
            num_arr[i] += (n // 10 + 1) * w

        for i in range(10 - remaining, 10):
            num_arr[i] -= w
        num_arr[0] -= w

        for number in str(n)[:-1]:
            num_arr[int(number)] -= remaining * w

        n //= 10
        w *= 10

    print(num_arr)


if __name__ == '__main__':
    main()

Now I cant get the result of 2 billion faster than 1 second! LOL