Google Interview Question: Find the n-th digit of a numb... | Glassdoor.com.au

## Interview Question

Software Engineer Interview

# Find the n-th digit of a number which is constructed by

concatenation of all natural numbers.

1

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

Interview Candidate on 20 Nov 2014
5

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 &gt; 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;
}
}

Mhret on 30 Nov 2014