LeetCode 400: Nth Digit Solution in Python – A Step-by-Step Guide

What Is LeetCode 400: Nth Digit?

In LeetCode 400: Nth Digit, you’re given a positive integer n, and you need to find the nth digit in the infinite sequence formed by concatenating all positive integers: 1234567891011121314.... For example, the 1st digit is 1, the 10th is 1 (from 10), and the 12th is 1 (from 11). The sequence starts with single digits (1-9), then two-digit numbers (10-99), three-digit numbers (100-999), and so on. Your job is to pinpoint that nth digit without writing out the whole thing!

Problem Statement

• Input: A positive integer n.
• Output: The nth digit (an integer 0-9) in the sequence 123456789101112....
• Rules:
• Count digits left to right.
• Sequence is infinite, starting from 1.

Constraints

• 1 <= n <= 10⁹ (up to a billion).

Examples

• Input: n = 3
• Output: 3 (sequence: 123, 3rd digit is 3).
• Input: n = 11
• Output: 0 (sequence: 12345678910, 11th digit is 0 from 10).
• Input: n = 12
• Output: 1 (sequence: 1234567891011, 12th digit is 1 from 11).

Understanding the Problem: Finding the Nth Spot

To solve LeetCode 400: Nth Digit in Python, we need to locate the nth digit in this endless string of numbers. A simple idea might be to write out the sequence and count digits—but with n up to a billion, that’s impossible! Instead, we’ll use:

• Best Solution (Mathematical Calculation): O(log n) time, O(1) space—uses math to jump to the right number.
• Alternative Solution (Brute Force): O(n) time, O(n) space—counts every digit (impractical for big n).

Let’s dive into the math-based solution with a clear, step-by-step explanation.

Best Solution: Mathematical Calculation

Why This Is the Best Solution

The mathematical calculation method is the champ because it’s lightning fast—O(log n) time and O(1) space. Instead of counting every digit, it figures out which group of numbers (1-digit, 2-digit, etc.) the nth digit falls in, then pinpoints the exact number and digit. It’s like using a map to zoom straight to your treasure instead of walking every step!

How It Works

Think of the sequence as a big book with chapters:

• Step 1: Count Digits by Chapter:
• Chapter 1: 1-9 (9 numbers, 1 digit each = 9 digits).
• Chapter 2: 10-99 (90 numbers, 2 digits each = 180 digits).
• Chapter 3: 100-999 (900 numbers, 3 digits each = 2700 digits).
• And so on.
• Step 2: Find the Right Chapter:
• Subtract the total digits of each chapter from n until you can’t anymore.
• That tells you how many digits long the number is (e.g., 2 digits for 10-99).
• Step 3: Locate the Number:
• Divide the remaining n by digits per number to find which number it’s in.
• Adjust for the starting number (e.g., 10 for 2-digit numbers).
• Step 4: Pick the Digit:
• Use the remainder to find which digit in that number (0-based index).
• Step 5: Why This Works:
• The sequence grows predictably: 9, 180, 2700, etc.
• Math lets us skip ahead without building the whole string.

It’s like flipping to the right page in a giant number book!

Step-by-Step Example

Example: n = 11

• Step 1: Count Chapters:
• 1-digit: 9 numbers × 1 = 9 digits, n = 11 > 9, subtract 9, n = 2.
• 2-digit: 90 numbers × 2 = 180 digits, n = 2 ≤ 180, stop here.
• Chapter: 2-digit numbers (10-99).
• Step 2: Find the Number:
• Digits per number = 2.
• Which number? (n-1) // 2 = (2-1) // 2 = 0 (0th number after 10).
• Start = 10, so number = 10 + 0 = 10.
• Step 3: Pick the Digit:
• Position in number: (n-1) % 2 = (2-1) % 2 = 1 (1st digit, 0-based).
• Number 10 as string: "10", index 1 = 0.
• Result: 0.

Example: n = 12

• Step 1:
• 1-digit: 9 digits, 12 > 9, n = 3.
• 2-digit: 180 digits, 3 ≤ 180, stop.
• Step 2:
• Digits = 2, (3-1) // 2 = 1, number = 10 + 1 = 11.
• Step 3:
• (3-1) % 2 = 0, "11"[0] = 1.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def findNthDigit(self, n: int) -> int:
        # Step 1: Adjust n to 0-based index
        n -= 1  # Convert to 0-based counting

        # Step 2: Find the chapter (digit length)
        digits = 1  # Start with 1-digit numbers
        count = 9   # 9 numbers (1-9)
        start = 1   # Starting number (1)

        while n >= digits * count:
            n -= digits * count  # Subtract digits in this chapter
            digits += 1          # Move to next digit length
            count *= 10          # 90, 900, etc.
            start *= 10          # 10, 100, etc.

        # Step 3: Find the number
        num = start + (n // digits)  # Which number in this chapter

        # Step 4: Find the digit
        digit_idx = n % digits       # Which digit in the number (0-based)
        num_str = str(num)           # Convert to string
        return int(num_str[digit_idx])  # Get and convert digit to int

• Line 4: Subtract 1 from n to make it 0-based (e.g., 11 becomes 10).
• Line 7-10: Set up for 1-digit numbers:
• digits: Length of numbers (1, 2, 3...).
• count: How many numbers (9, 90, 900...).
• start: First number (1, 10, 100...).
• Line 12-16: Loop to find chapter:
• If n ≥ total digits in chapter (digits * count), subtract and move to next chapter.
• E.g., n = 10, 10 > 9, n = 1, digits = 2, count = 90, start = 10.
• Line 19: Calculate the number:
• n // digits is the offset from start (e.g., 1 // 2 = 0, num = 10).
• Line 22-24: Get the digit:
• n % digits is the position (e.g., 1 % 2 = 1).
• Convert num to string, grab digit, convert back to int.
• Time Complexity: O(log n)—loop runs log n times (base 10).
• Space Complexity: O(1)—just a few variables.

This is like a math shortcut to the nth digit!

Alternative Solution: Brute Force String Concatenation

Why an Alternative Approach?

The brute force method builds the sequence as a string and picks the nth digit. It’s O(n) time and O(n) space—way too slow and heavy for big n, but it’s a clear way to see what’s happening. It’s like writing out the whole book and flipping to the page you need!

How It Works

Picture it as writing the sequence:

• Step 1: Start with 1, add 2, 3, ..., until you have n digits.
• Step 2: Grab the nth digit from the string.
• Step 3: Return it.

Step-by-Step Example

Example: n = 11

• Build: "12345678910".
• Pick: 11th digit (1-based) = "10"[1] = 0.
• Result: 0.

Code for Brute Force Approach

Copy codeclass Solution:
    def findNthDigit(self, n: int) -> int:
        sequence = ""
        num = 1
        while len(sequence) < n:
            sequence += str(num)
            num += 1
        return int(sequence[n-1])

• Time Complexity: O(n)—builds string up to n digits.
• Space Complexity: O(n)—stores the string.

It’s a slow but sure count!

Comparing the Two Solutions

• Mathematical Calculation (Best):
• Pros: O(log n), O(1), super fast.
• Cons: Math to understand.
• Brute Force (Alternative):
• Pros: O(n), O(n), easy to follow.
• Cons: Impractical for big n.

Math wins big.

Additional Examples and Edge Cases

• 1: 1 (1st digit).
• 9: 9 (9th digit).
• 10: 1 (10th digit from 10).

Math handles all.

Complexity Breakdown

• Mathematical Calculation: Time O(log n), Space O(1).
• Brute Force: Time O(n), Space O(n).

Math’s the speed champ.

Key Takeaways

• Math Calculation: Jump to it!
• Brute Force: Count it out!
• Sequences: Patterns rule.
• Python Tip: Strings are handy—see [Python Basics](/python/basics).

Final Thoughts: Grab That Digit

LeetCode 400: Nth Digit in Python is a number-sequence treasure hunt. The math method zooms to the answer, while brute force trudges along. Want more number fun? Try LeetCode 202: Happy Number or LeetCode 263: Ugly Number. Ready to count? Head to Solve LeetCode 400 on LeetCode and snag that nth digit today!