Efficient algorithm to find the n-th digit in the string 112123123412345

Question

What is an efficient algorithm for finding the digit in nth position in the following string

112123123412345123456 ... 123456789101112 ...

Storing the entire string in memory is not feasible for very large n, so I am looking for an algorithm that can find the nth digit in the above string which works if n is very large (i.e. an alternative to just generating the first n digits of the string).

Answer 1

There are several levels here: the digit is part of a number x, the number x is part of a sequence 1,2,3...x...y and that sequence is part of a block of sequences that lead up to numbers like y that have z digits. We'll tackle these levels one by one.

There are 9 numbers with 1 digit:

first: 1 (sequence length: 1 * 1)  
last: 9 (sequence length: 9 * 1)  
average sequence length: (1 + 9) / 2 = 5  
1-digit block length: 9 * 5 = 45  

There are 90 numbers with 2 digits:

first: 10 (sequence length: 9 * 1 + 1 * 2)  
last: 99 (sequence length: 9 * 1 + 90 * 2)  
average sequence length: 9 + (2 + 180) / 2 = 100  
2-digit block length: 90 * 100 = 9000  

There are 900 numbers with 3 digits:

first: 100 (sequence length: 9 * 1 + 90 * 2 + 1 * 3)  
last: 999 (sequence length: 9 * 1 + 90 * 2 + 900 * 3)  
average sequence length: 9 + 180 + (3 + 2,700) / 2 = 1,540.5  
3-digit block length: 900 * 1,540.5 = 1,386,450  

If you continue to calculate these values, you'll find which block (of sequences up to how many digits) the digit you're looking for is in, and you'll know the start and end point of this block.

Say you want the millionth digit. You find that it's in the 3-digit block, and that this block is located in the total sequence at:

start of 3-digit block: 45 + 9,000 + = 9,045  
start of 4-digit block: 45 + 9,000 + 1,386,450 = 1,395,495  

So in this block we're looking for digit number:

1,000,000 - 9,045 = 990,955  

Now you can use e.g. a binary search to find which sequence the 990,955th digit is in; you start with the 3-digit number halfway in the 3-digit block:

first: 100 (sequence length: 9 + 180 + 1 * 3)  
number: 550 (sequence length: 9 + 180 + 550 * 3)  
average sequence length: 9 + 180 + (3 + 1650) / 2 = 1,015.5  
total sequence length: 550 * 1,015.5 = 558,525  

Which is too small; so we try 550 * 3/4 = 825, see if that is too small or large, and go up or down in increasingly smaller steps until we know which sequence the 990,995th digit is in.

Say it's in the sequence for the number n; then we calculate the total length of all 3-digit sequences up to n-1, and this will give us the location of the digit we're looking for in the sequence for the number n. Then we can use the numbers 9*1, 90*2, 900*3 ... to find which number the digit is in, and then what the digit is.