Code Implementation

class Solution:
    def findNthDigit(self, n: int) -> int:
        digit_length = 1
        count = 9
        start = 1
        # Find the range in which the nth digit falls
        while n > digit_length * count:
            n -= digit_length * count
            digit_length += 1
            count *= 10
            start *= 10
        # Find the actual number where the nth digit is located
        num = start + (n - 1) // digit_length
        # Find the digit in the number
        digit_index = (n - 1) % digit_length
        return int(str(num)[digit_index])
      

class Solution {
public:
    int findNthDigit(int n) {
        long long digitLength = 1, count = 9, start = 1;
        while (n > digitLength * count) {
            n -= digitLength * count;
            digitLength++;
            count *= 10;
            start *= 10;
        }
        int num = start + (n - 1) / digitLength;
        int digitIndex = (n - 1) % digitLength;
        string numStr = to_string(num);
        return numStr[digitIndex] - '0';
    }
};
      

class Solution {
    public int findNthDigit(int n) {
        int digitLength = 1;
        long count = 9;
        int start = 1;
        while (n > digitLength * count) {
            n -= digitLength * count;
            digitLength++;
            count *= 10;
            start *= 10;
        }
        int num = start + (n - 1) / digitLength;
        int digitIndex = (n - 1) % digitLength;
        return Integer.toString(num).charAt(digitIndex) - '0';
    }
}
      

var findNthDigit = function(n) {
    let digitLength = 1, count = 9, start = 1;
    while (n > digitLength * count) {
        n -= digitLength * count;
        digitLength++;
        count *= 10;
        start *= 10;
    }
    let num = start + Math.floor((n - 1) / digitLength);
    let digitIndex = (n - 1) % digitLength;
    return Number(num.toString()[digitIndex]);
};
      

Problem Description

Given an integer n, you are to find the nth digit in the infinite sequence of all positive integers concatenated together: 123456789101112... and so on.
For example, the 3rd digit is 3, the 11th digit is 0 (from 10).
Constraints:

• 1 ≤ n ≤ 2³¹ - 1
• There is always exactly one valid answer
• Each number is used only once in the sequence

Thought Process

At first glance, it might seem like you should build the sequence by concatenating numbers until you reach the nth digit. However, this is very inefficient, especially for large n (up to 2 billion).
Instead, we need to find a way to "jump" directly to the region of the sequence that contains the nth digit.
The key insight is that numbers with the same digit length contribute a predictable amount of digits. For example:

• Single-digit numbers (1-9): 9 numbers, 1 digit each
• Two-digit numbers (10-99): 90 numbers, 2 digits each
• Three-digit numbers (100-999): 900 numbers, 3 digits each

Solution Approach

The optimized solution follows these steps:

1. Determine the digit length: Start with 1-digit numbers, then 2-digit, 3-digit, and so on. For each group, calculate how many digits it contributes (count * digit_length). Subtract this from n until the group containing the nth digit is found.
2. Find the actual number: Once we know the digit length, the starting number (start) for that group, and the offset, we can compute which number contains the nth digit.
   • The number is start + (n - 1) // digit_length
3. Locate the digit within the number: The digit's index inside the number is (n - 1) % digit_length.
4. Return the result: Convert the number to a string and pick the digit at the calculated index.

Example Walkthrough

Example: n = 15

• 1-digit numbers: 9 digits (1-9). n = 15 is greater than 9, so subtract 9: n = 6
• 2-digit numbers: Each has 2 digits, 90 numbers (10-99), total 180 digits. n = 6 is less than 180, so the digit is in this group.
• Start of 2-digit numbers is 10.
• Which number? (n-1) // 2 = (6-1)//2 = 2. So, 2 numbers after 10: 10, 11, 12
• Digit index: (n-1) % 2 = (6-1)%2 = 1
• Number is 12, index 1 (second digit), so the answer is 2.
• Check: The sequence is 123456789101112... The 15th digit is '2'.

Time and Space Complexity

Brute-force: O(n) time and space, since you would need to build the sequence up to the nth digit.
Optimized Approach:

• Time complexity: O(log n). At each step, we multiply digit length and count by 10, so the number of iterations is proportional to the number of digits in n (which is at most 10 for 32-bit integers).
• Space complexity: O(1). Only a few variables are used; no extra space is required.

Summary

The problem asks for the nth digit in an infinite concatenation of positive integers. The key insight is to avoid brute-force concatenation and instead use arithmetic to "jump" to the correct digit's group, then compute the exact number and digit. This results in a fast, elegant solution with logarithmic time complexity and constant space usage.