# Nth Digit
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/nth-digit)
Canonical: https://scaleengineer.com/dsa/problems/nth-digit
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## Problem
Given an integer `n`, return the `nth` digit of the infinite integer sequence `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]`.

**Example 1:**

**Input:** n = 3
**Output:** 3

**Example 2:**

**Input:** n = 11
**Output:** 0
**Explanation:** The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

**Constraints:**

* `1 <= n <= 231 - 1`

# Approaches
## Brute-Force Simulation
This approach simulates the creation of the infinite integer sequence `[1, 2, 3, ...]` digit by digit. We iterate through numbers, and for each number, we check if the `n`th digit falls within its string representation.
**Time:** O(N). To find the Nth digit, the loop iterates through approximately `N / log10(N)` numbers. Inside the loop, converting a number `i` to a string takes `O(log10(i))` time. The total complexity is roughly the sum of `log10(i)` for `i` up to `N/logN`, which is approximately `O(N)`. This will result in a 'Time Limit Exceeded' error for large N. · **Space:** O(log N). The space is dominated by storing the string representation of the current number, which has a length of `O(log N)`.
**Pros:** Conceptually simple and easy to implement.; Correct for small values of `n`.
**Cons:** Extremely inefficient for large values of `n` as specified in the constraints.; Will not pass the time limits on most platforms.
### Explanation
The most intuitive way to solve this problem is to simulate the process directly. We can generate the sequence of numbers starting from 1 and keep track of the total number of digits seen so far.

The algorithm proceeds as follows:
*   Start with the number `i = 1`.
*   In a loop, convert the current number `i` to its string representation.
*   Let the length of this string be `len`.
*   If our target index `n` is less than or equal to `len`, it means the digit we are looking for is within the current number `i`. The desired digit is the `(n-1)`th character of the string.
*   Otherwise, the digit is in a subsequent number. We subtract `len` from `n` to move our target index forward and increment `i` to consider the next number.
*   This process continues until the `n`th digit is found.

For example, if `n = 11`:
1. `num=1`, `s="1"`, `len=1`. `11 > 1`. `n` becomes `11-1=10`.
2. `num=2`, `s="2"`, `len=1`. `10 > 1`. `n` becomes `10-1=9`.
...
9. `num=9`, `s="9"`, `len=1`. `3 > 1`. `n` becomes `2`.
10. `num=10`, `s="10"`, `len=2`. `2 <= 2`. The digit is in "10". It's the `(2-1)=1`st character, which is '0'.

```java
class Solution {
    public int findNthDigit(int n) {
        // This approach is too slow and will cause Time Limit Exceeded for large n.
        int num = 1;
        while (true) {
            String s = Integer.toString(num);
            int len = s.length();
            if (n <= len) {
                return Character.getNumericValue(s.charAt(n - 1));
            }
            n -= len;
            num++;
        }
    }
}
```
### Algorithm
*   Initialize a counter `num = 1`.
*   Start an infinite loop.
*   Convert `num` to its string representation `s`.
*   Get the length of the string, `len`.
*   If `n` is less than or equal to `len`, the target digit is within the current number. Return the digit at index `n-1` of `s`.
*   Otherwise, subtract `len` from `n` and increment `num` to proceed to the next number.

## Mathematical Calculation
This efficient approach avoids simulation by mathematically determining which number contains the `n`th digit and then pinpointing the digit itself. It works by analyzing the number of digits for numbers of different lengths (1-digit, 2-digit, etc.).
**Time:** O(log N). The `while` loop runs at most about 9-10 times for `N` up to `2^31 - 1`, as the number of digits in `N` is `O(log10(N))`. All other operations (arithmetic, string conversion) also take time proportional to the number of digits, so the overall complexity is logarithmic. · **Space:** O(log N). This space is used to store the string representation of the target number. Since the number of digits in the target number is `O(log N)`, the space complexity is logarithmic. This is often considered O(1) constant space as it's very small.
**Pros:** Highly efficient and fast, easily passing time limits for large `n`.; Scales well with even larger inputs.
**Cons:** The logic is more complex than the brute-force approach.; Requires careful handling of integer types to avoid overflow (using `long` is recommended).
### Explanation
Instead of generating the sequence, we can deduce the location of the `n`th digit by observing the pattern of how many digits are contributed by numbers of a certain length.
- 1-digit numbers (1-9): 9 numbers × 1 digit/number = 9 digits
- 2-digit numbers (10-99): 90 numbers × 2 digits/number = 180 digits
- 3-digit numbers (100-999): 900 numbers × 3 digits/number = 2700 digits
- In general, `d`-digit numbers: `9 * 10^(d-1)` numbers × `d` digits/number.

The algorithm has three main steps:
1.  **Find the number of digits (`digits`) of the target number.** We loop, subtracting the total digits for each group (1-digit numbers, 2-digit numbers, etc.) from `n` until `n` falls within the range of the current group.
2.  **Find the specific number (`num`) that contains the digit.** Once we know the number of digits (`digits`), the remaining value of `n` tells us how far into that group the digit is. The target number can be calculated as `start_number + (n - 1) / digits`.
3.  **Find the actual digit.** The index of the digit within the target number is given by `(n - 1) % digits`. We can then extract this digit from the number.

Let's trace with `n = 11`:
- **Step 1:** The digit is not in a 1-digit number (since `11 > 9`). We subtract 9 from `n`, so `n` becomes `2`. We now look for the 2nd digit among all 2-digit numbers.
- **Step 2:** The numbers are 2-digit (`digits = 2`). The first 2-digit number is 10 (`start = 10`). The target number is `10 + (2 - 1) / 2 = 10 + 0 = 10`.
- **Step 3:** The index of the digit within the number 10 is `(2 - 1) % 2 = 1`. The digit at index 1 of "10" is '0'.

It's crucial to use `long` for intermediate calculations involving the count of numbers to prevent integer overflow, as `n` can be large.

```java
class Solution {
    public int findNthDigit(int n) {
        // Use long to prevent overflow, as count can become large
        long count = 9;
        int digits = 1;
        long start = 1;

        // 1. Find the length of the number where the nth digit is
        while (n > digits * count) {
            n -= digits * count;
            digits++;
            count *= 10;
            start *= 10;
        }

        // 2. Find the actual number
        // n is now 1-based index within the current digit-length group
        long num = start + (n - 1) / digits;

        // 3. Find the digit within the number
        // (n - 1) % digits gives the 0-based index of the digit
        String s = Long.toString(num);
        char digitChar = s.charAt((n - 1) % digits);
        
        return Character.getNumericValue(digitChar);
    }
}
```
### Algorithm
*   Initialize variables: `digits = 1`, `count = 9` (number of `d`-digit numbers), `start = 1` (the first `d`-digit number).
*   Use a `while` loop to find the correct group of numbers (e.g., 1-digit, 2-digit, etc.). The loop continues as long as `n` is larger than the total number of digits in the current group (`digits * count`).
*   Inside the loop, update `n` by subtracting the digits of the processed group. Then, increment `digits` and update `count` and `start` for the next group (e.g., `count *= 10`, `start *= 10`).
*   After the loop, `n` represents the 1-based index of the digit within the current group.
*   Calculate the target number: `num = start + (n - 1) / digits`.
*   Calculate the 0-based index of the digit within the number: `index = (n - 1) % digits`.
*   Convert `num` to a string and extract the character at `index`.
*   Convert the character to an integer and return it.

# Solutions
### CSharp

```csharp
public class Solution {
    public int FindNthDigit(int n) {
        int k = 1, cnt = 9;
        while ((long) k * cnt < n) {
            n -= k * cnt;
            ++k;
            cnt *= 10;
        }
        int num = (int) Math.Pow(10, k - 1) + (n - 1) / k;
        int idx = (n - 1) % k;
        return num.ToString()[idx] - '0';
    }
}
```

### Java

```java
class Solution { public int findNthDigit ( int n ) { int k = 1 , cnt = 9 ; while (( long ) k * cnt < n ) { n -= k * cnt ; ++ k ; cnt *= 10 ; } int num = ( int ) Math . pow ( 10 , k - 1 ) + ( n - 1 ) / k ; int idx = ( n - 1 ) % k ; return String . valueOf ( num ). charAt ( idx ) - '0' ; } }
```

### JavaScript

```javascript
/** * @param {number} n * @return {number} */ var findNthDigit = function (n) {
  let k = 1,
    cnt = 9;
  while (k * cnt < n) {
    n -= k * cnt;
    ++k;
    cnt *= 10;
  }
  const num = Math.pow(10, k - 1) + (n - 1) / k;
  const idx = (n - 1) % k;
  return num.toString()[idx];
};

```

### CPP

```cpp
class Solution { public: int findNthDigit ( int n ) { int k = 1 , cnt = 9 ; while ( 1ll * k * cnt < n ) { n -= k * cnt ; ++ k ; cnt *= 10 ; } int num = pow ( 10 , k - 1 ) + ( n - 1 ) / k ; int idx = ( n - 1 ) % k ; return to_string ( num )[ idx ] - '0' ; } };
```

### Python

```python
class Solution : def findNthDigit ( self , n : int ) -> int : k , cnt = 1 , 9 while k * cnt < n : n -= k * cnt k += 1 cnt *= 10 num = 10 ** ( k - 1 ) + ( n - 1 ) // k idx = ( n - 1 ) % k return int ( str ( num )[ idx ])
```