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.
Answer

Interview Answer

2 Answers

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 > 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.