Domain 2MediumCORE

Nth Digit

We are given an integer n representing a position in an infinite sequence formed by concatenating all positive integers: [1, 2, 3, ..., 9, 10, 11, ...]. The goal is to return the single digit at that specific index (1-based).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math

400. Nth Digit

Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 32.4%


Problem Breakdown

We are given an integer n representing a position in an infinite sequence formed by concatenating all positive integers: [1, 2, 3, ..., 9, 10, 11, ...]. The goal is to return the single digit at that specific index (1-based).

Inputs:

  • n: An integer representing the position in the sequence. Range [1,231−1][1, 2^{31} - 1].

Outputs:

  • A single integer between 0 and 9 inclusive.

Constraints & Edge Cases:

  • Large Input: Since n can be up to ≈2×109\approx 2 \times 10^9, a brute-force string construction or iteration is impossible (Time Limit Exceeded). We need an O(log⁡n)O(\log n) approach relative to the value of digits.
  • Zero Digits: The sequence starts at ‘1’. However, numbers like “10”, “20” contain zeros. Our logic must correctly identify these as valid targets for n.
  • Boundary Conditions: We need to handle cases where n falls exactly on the boundary between digit groups (e.g., transitioning from 9-digit sequences of length-1 numbers to length-2).

Intuition

If we try a naive approach, we might simulate building the string “123456789…” until its length matches n. However, for n=2×109n = 2 \times 10^9, this sequence would contain billions of digits. Storing or iterating through that is infeasible (O(n)O(n) time/space).

The key insight is to recognize the pattern in how many digits are contributed by numbers of a specific length:

  • Length 1: Numbers 1 to 9. There are 99 such numbers, contributing 9×1=99 \times 1 = 9 total digits.
  • Length 2: Numbers 10 to 99. There are 9090 such numbers (99−10+199 - 10 + 1), contributing 90×2=18090 \times 2 = 180 total digits.
  • Length k: Generally, there are 9×10k−19 \times 10^{k-1} numbers of length k.

We can subtract the counts of these groups from our target index n until we find which group (length) contains our digit. Once inside a specific group, we know exactly how many full numbers have passed and what position within that number corresponds to our remaining offset. This allows us to calculate the answer mathematically without constructing the string.

Approach

  1. Determine Group Length: Start with len = 1 (representing single-digit numbers). Calculate how many digits exist in this group (count * len). If n is greater than that, subtract it from n, increment len, and update the count of available numbers for the next length.
  2. Identify Target Number: Once we find the correct length group where n fits:
    • The remaining n tells us how far into this specific block of digits we are.
    • We calculate which number in that sequence contains our digit using integer division by len. This gives us an offset from the first number of that length (e.g., 10 for len=2).
  3. Extract Digit: Convert the identified target number to a string and pick the character at index (n - 1) % len (using 0-based indexing relative to the start of the digit sequence within that specific number).

Complexity Analysis

  • Time Complexity: O(log⁡10n)O(\log_{10} n) or effectively constant for standard integer limits. We iterate through lengths len = 1, 2, .... Since we are dealing with a 32-bit signed integer limit (n≈2×109n \approx 2 \times 10^9), the maximum number of digits in our sequence is roughly bounded by log⁡10(n)\log_{10}(n) iterations (roughly 5-6 loops for this constraint).
  • Space Complexity: O(1)O(1). We only store a few integer variables.

Solution

class Solution:
    def findNthDigit(self, n: int) -> int:
        # Step 1: Find the length of numbers that contain our nth digit
        len = 1      # Current number length (starts at single digits)
        count = 9    # Count of numbers with current length (e.g., 1-9 for len=1)
        
        while n > len * count:
            n -= len * count       # Skip all digits in the current group
            len += 1               # Move to next number length
            count *= 10           # Update count of numbers (e.g., 9 -> 90 for len=2)

        # Step 2: Determine which specific number contains our digit
        # We have 'n' remaining digits within the current group. 
        # The first number in this group is pow(10, len - 1).
        
        target_number = (pow(10, len - 1)) + ((n - 1) // len)

        # Step 3: Extract the specific digit from that number
        return int(str(target_number)[(n - 1) % len])

Edge Cases Handled

  • Small n (e.g., n=1 to 9): The loop condition fails immediately, logic correctly returns digits ‘1’ through ‘9’.
  • Transition points: When n falls exactly at the end of a group (e.g. after digit ‘9’), the subtraction ensures we enter the next length calculation with correct offset.
  • Large n: The loop runs logarithmically, preventing overflow or timeout even near 231−12^{31}-1. Python handles large integers natively so intermediate calculations won’t crash on standard 64-bit limits.