How to reduce time to find the n-th place from consecutive digits number for less than 1 second

I'm following the programming test, and there are questions like this

From this consecutive digits:

123456789101112131415161718192021....

For example The 10th digit is 1 The 11th digit is 0 and so on

What is the 1,000,000th digit?

What is the 1,000,000,000th digit?

What is the 1,000,000,000,000th digit?

Your solution should run below 1 second.

I've been made an answer but still more than 1 second. I try to use polynominal.

So, how I can reduce the time to find n-th place from digits above?

This is my answer, (PHP):

function digit_pol ($n) {

  $counter = 1;
  $digit_arr = array();

  for ($i = 1; $i <= $n; $i++) {

    for ($j = 0; $j < strlen($i); $j++) {

      // If array more than 100, always shift (limit array length to 11)
      if($i > 10) {
        array_shift($digit_arr);
      }

      // Fill array
      $digit_arr[$counter] = substr($i, $j, 1);

      // Found
      if($counter == $n) {
        return $digit_arr[$counter];
      }

      $counter++;
    }

  }

}

/**
 * TESTING
 */

$find_place = 1000000;

$result = digit_pol($find_place);

echo "Digit of " . $find_place . "th is <b>" . $result . "</b>";

Solution

What's important to realize is that it's easy to take big steps:

1 digit numbers: 123456789           -   9 * 1 digit
2 digit numbers: 101112...9899       -  90 * 2 digits
3 digit numbers: 100101102...998999  - 900 * 3 digits
4 digit numbers: ...

Now you can do a recursive solution that skips over 9×10^k×k digits at a time, until you reach the base case where n is in the range of digits in the current magnitude.

When you know which particular range to look in, it's fairly easy to find the nth digit. First divide n by the length of each number. That turns the digit offset into the number offset. Now add 10^k to that to get the actual number to look in. At that point it's a matter of finding a specific digit in a given number.

Take for example n = 1234:

n > 9, so it's not in the single digit range:
- Skip over the single digit range (i.e. n -= 9) and continue on 2 digit numbers...
n > 90 * 2 so it's not in the two digit range either
- Skip over the 2-digit range (i.e. n -= 90*2) and continue on 3 digit numbers...
Now n < 900 * 3 so we're looking for a digit in the 100101102... sequence
Since each number in this sequence is 3 digits long, we can find which particular number to look in by doing 100 + n / 3. In this case this equals 448.
We now simply compute n % 3 (which equals 1 in this case) to find which digit to pick. The end result is thus 4.

Here's a solution in Java:

public static char nthDigit(int n, int digitsInFirstNum) {
    int magnitude = (int) Math.pow(10, digitsInFirstNum - 1);
    int digitsInMagnitude = 9 * magnitude * digitsInFirstNum;

    if (n < digitsInMagnitude) {
        int number = magnitude + n / digitsInFirstNum;
        int digitPos = n % digitsInFirstNum;
        return String.valueOf(number).charAt(digitPos);
    }

    return nthDigit(n - digitsInMagnitude, digitsInFirstNum + 1);
}

public static char nthDigit(int n) {
    return nthDigit(n, 1);
}