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

what efficient algorithm finding digit in nth position in following string

112123123412345123456 ... 123456789101112 ... 

storing entire string in memory not feasible large n, looking algorithm can find nth digit in above string works if n large (i.e. alternative generating first n digits of string).

there several levels here: digit part of number x, number x part of sequence 1,2,3...x...y , sequence part of block of sequences lead numbers y have z digits. we'll tackle these levels 1 one.

there 9 numbers 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 90 numbers 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 900 numbers 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 continue calculate these values, you'll find block (of sequences how many digits) digit you're looking in, , you'll know start , end point of block.

say want millionth digit. find it's in 3-digit block, , block located in 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 block we're looking digit number:

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

now can use e.g. binary search find sequence 990,955th digit in; start 3-digit number halfway in 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 small; try 550 * 3/4 = 825, see if small or large, , go or down in increasingly smaller steps until know sequence 990,995th digit in.

say it's in sequence number n; calculate total length of 3-digit sequences n-1, , give location of digit we're looking in sequence number n. can use numbers 9*1, 90*2, 900*3 ... find number digit in, , digit is.