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>";
```

# Best How To :

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

th 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);
}
```