# LeetCode 400: Nth Digit

## Problem Restatement

We are given an integer `n`.

Consider the infinite sequence formed by writing positive integers one after another:

```text
123456789101112131415...
```

We need to return the `n`th digit in this sequence.

The position is 1-indexed.

For example:

```text
n = 3
```

The third digit is `3`.

For:

```text
n = 11
```

The sequence begins:

```text
12345678910...
```

The 11th digit is `0`, from the number `10`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | The `n`th digit as an integer |
| Sequence | `1, 2, 3, 4, ..., 10, 11, ...` concatenated |
| Constraint | `1 <= n <= 2^31 - 1` |

Example function shape:

```python
def findNthDigit(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 3
```

The sequence starts:

```text
1 2 3 4 5 6 7 8 9 ...
```

The third digit is:

```python
3
```

Example 2:

```python
n = 11
```

The sequence starts:

```text
1 2 3 4 5 6 7 8 9 1 0 1 1 ...
```

The 10th digit is `1`, the first digit of `10`.

The 11th digit is `0`, the second digit of `10`.

So the answer is:

```python
0
```

## First Thought: Build the String

A direct solution is to build the sequence until it has at least `n` digits.

```python
sequence = "123456789101112..."
```

Then return:

```python
int(sequence[n - 1])
```

This is easy, but `n` can be as large as `2^31 - 1`.

Building such a long string is too slow and uses too much memory.

We need to jump directly to the right number.

## Key Insight

Numbers can be grouped by digit length.

| Group | Numbers | Count of numbers | Digits contributed |
|---|---|---:|---:|
| 1-digit | `1` to `9` | `9` | `9 * 1 = 9` |
| 2-digit | `10` to `99` | `90` | `90 * 2 = 180` |
| 3-digit | `100` to `999` | `900` | `900 * 3 = 2700` |

In general, for `digit_len` digits:

```text
count = 9 * 10^(digit_len - 1)
```

and the group contributes:

```text
count * digit_len
```

So we can subtract whole groups until `n` falls inside one group.

## Algorithm

Start with the 1-digit group:

```python
digit_len = 1
start = 1
count = 9
```

While `n` is larger than the total digits in the current group:

```python
n -= digit_len * count
digit_len += 1
start *= 10
count *= 10
```

After this loop, the target digit is inside the group starting at `start`.

Now `n` is the position inside that group, still 1-indexed.

Find the exact number:

```python
number = start + (n - 1) // digit_len
```

Find the digit index inside that number:

```python
index = (n - 1) % digit_len
```

Return:

```python
int(str(number)[index])
```

## Walkthrough

Let:

```python
n = 11
```

The 1-digit group contributes `9` digits.

Since `11 > 9`, subtract it:

```python
n = 11 - 9 = 2
```

Now we are in the 2-digit group:

```python
10, 11, 12, ...
```

The second digit in this group is inside `10`.

Compute the number:

```python
start = 10
digit_len = 2

number = 10 + (2 - 1) // 2
       = 10
```

Compute the digit index:

```python
index = (2 - 1) % 2
      = 1
```

The digit at index `1` in `"10"` is:

```python
"0"
```

So the answer is:

```python
0
```

## Correctness

The sequence is divided into groups by digit length.

For each digit length `d`, there are exactly `9 * 10^(d - 1)` positive integers with `d` digits. Therefore that group contributes exactly:

```text
d * 9 * 10^(d - 1)
```

digits to the infinite sequence.

The algorithm subtracts complete groups while the target position lies after them. When the loop stops, `n` is the position of the desired digit inside the current digit-length group.

Inside that group, every number contributes exactly `digit_len` digits. Therefore `(n - 1) // digit_len` gives the zero-based offset of the target number from `start`, and `(n - 1) % digit_len` gives the digit position inside that number.

Thus `number = start + (n - 1) // digit_len` is exactly the number containing the target digit, and `index = (n - 1) % digit_len` is exactly the target digit's index inside that number.

Returning that digit gives the correct `n`th digit of the infinite sequence.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | We move through digit-length groups |
| Space | `O(1)` | Only a few integer variables are used |

For 32-bit `n`, there are at most 10 digit-length groups.

## Implementation

```python
class Solution:
    def findNthDigit(self, n: int) -> int:
        digit_len = 1
        start = 1
        count = 9

        while n > digit_len * count:
            n -= digit_len * count
            digit_len += 1
            start *= 10
            count *= 10

        number = start + (n - 1) // digit_len
        index = (n - 1) % digit_len

        return int(str(number)[index])
```

## Code Explanation

We begin with the 1-digit group:

```python
digit_len = 1
start = 1
count = 9
```

`digit_len` is the number of digits per number in the current group.

`start` is the first number in that group.

`count` is how many numbers are in that group.

This loop skips full groups:

```python
while n > digit_len * count:
```

After skipping a group, we move to the next digit length:

```python
n -= digit_len * count
digit_len += 1
start *= 10
count *= 10
```

When the loop ends, the answer is inside the current group.

The target number is:

```python
number = start + (n - 1) // digit_len
```

The target digit position inside that number is:

```python
index = (n - 1) % digit_len
```

Finally:

```python
return int(str(number)[index])
```

## Testing

```python
def test_solution():
    s = Solution()

    assert s.findNthDigit(1) == 1
    assert s.findNthDigit(3) == 3
    assert s.findNthDigit(9) == 9
    assert s.findNthDigit(10) == 1
    assert s.findNthDigit(11) == 0
    assert s.findNthDigit(12) == 1
    assert s.findNthDigit(13) == 1

    assert s.findNthDigit(189) == 9
    assert s.findNthDigit(190) == 1
    assert s.findNthDigit(191) == 0
    assert s.findNthDigit(192) == 0

    assert s.findNthDigit(1000) == 3

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `1`, `3`, `9` | Inside the 1-digit group |
| `10`, `11` | First digits of number `10` |
| `12`, `13` | Digits of number `11` |
| `189` | Last digit of the 2-digit group |
| `190` | First digit of the 3-digit group |
| `191`, `192` | Remaining digits of number `100` |
| `1000` | Larger position inside 3-digit group |