The number of numbers in the concatenated string that have k digits is

9 * 10 ^ (k - 1)

For example, there are 9 * 10 ^ (2 - 1) = 90 two digit numbers.

So the problem is to find which number of digits region the given n falls. To find that we subtract the length of each region from digit 1 to k from the given number until we get a negative number.

Once we determine which region n falls in, we can determine which exact number it falls on.

Below is a C++ implementation:

int nthDigit(int n) {

int k = 0;

while( n > 0) {

k++;

n -= 9 * pow(10, k - 1) * k;

}

n += 9 * pow(10, k - 1) * k;

if( n % k == 0) {

int finalNumber = pow(10, k - 1) + (n / k) - 1;

return finalNumber % 10;

} else {

int finalNumber = pow(10, k - 1) + (n / k);

return static_cast((finalNumber / pow(10, k - (n % k)))) % 10;

}

}

Here I was blocked. An elegant solution came to me a little late on the next day.