Stack 1,10,100,1000,10000,100000,... vertically:

1
10
100
1000
10000
100000
...
the cumulative sums of digits from the top are:
1,3,6,10,15,21,... which are in the form of combination(N,2) = N*(N-1)/2

checking whether one is at Kth digit is the same as finding if there is integer solution to:
N*(N-1)/2 = K-1

one way is to solve the quadratic equation for N (in double) and cast N to integer and check the above relation.
regards,
So Sui Ming



Edited by author 16.01.2024 19:27

Edited by author 16.01.2024 19:27

Great solution, So Sui Ming, I did not think about that one in particular.

I just use prefix sums and binary search.

If you write down the sequence and it's index starting from 1.

You will notice that if you do prefix sum ( half interval way , so starting from 0, the first element, first element + second element, etc. ) up till  sum <= MAX ( 2^31 - 1 ), you will get 65535 numbers in a sorted way.

In this way, notice, that the numbers in this prefix_sum array are all index s.t. digit = 1.

You still need to +1 in every position of prefix_sum array, because of 1-index of input.

Now you read input number K and do binary search on the prefix sum array.

If you did find, great! It is 1.
Otherwise, it is 0.