"Digit Queries" CSES Solution giving TLE I really need a more accurate way to size inf_string. This code works but gets exponentially more inefficient the bigger max(queries) is, and therefore just can't hold up to the gargantuan numbers that CSES throws into it.
Problem:
Consider an infinite string that consists of all positive integers in increasing order:
12345678910111213141516171819202122232425...
Your task is to process q queries of the form: what is the digit at position k in the string?
The first input line has an integer q: the number of queries.
After this, there are q lines that describe the queries. Each line has an integer k: a 1-indexed position in the string. For each query, print the corresponding digit.
queries = []
for i in range(int(input())):
    queries.append(int(input()))
# TODO FIND A BETTER WAY TO LIMIT inf_string LENGTH
inf_string = [str(x) for x in range(1, max(queries)+1)]
inf_string = &quot;&quot;.join(inf_string)
for k in queries:
    print(inf_string[k-1])
Building or iterating the whole string takes far too long. Instead group the numbers by length:
length 1 digit:  1 to 9 -&gt; 9 numbers =&gt; 9 digits total
length 2 digits: 10 to 99 -&gt; 90 numbers =&gt; 180 digits total
length 3 digits: 100 to 999 -&gt; 900 numbers =&gt; 2700 digits total
length 4 digits: 1000 to 9999 -&gt; 9000 numbers =&gt; 36000 digits total
etc

The number of digits per group (9, 180, 2700, 36000, etc) are easy to compute. Skip these groups of equal-length numbers until you reach the right group (the remaining k falls into it). Then just compute the right number inside the group and get the right digit from it.
for _ in range(int(input())):
    k = int(input())

    length = 1
    while k &gt; 9 * 10**(length-1) * length:
        k -= 9 * 10**(length-1) * length
        length += 1
    q, r = divmod(k-1, length)
    print(str(10**(length-1) + q)[r])

Takes about 0.03 seconds of the allowed 1 second.
Or keeping 10**(length-1) in a variable for less duplication:
for _ in range(int(input())):
    k = int(input())

    length = first = 1
    while k &gt; 9 * first * length:
        k -= 9 * first * length
        length += 1
        first *= 10
    q, r = divmod(k-1, length)
    print(str(first + q)[r])