Problem Description

You are given an infinite sequence of integers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... written as a continuous string of digits: 123456789101112...

Your task is to find the nth digit in this infinite digit sequence.

For example:

• The 1st digit is 1 (from number 1)
• The 5th digit is 5 (from number 5)
• The 11th digit is 0 (from number 10, specifically the second digit)
• The 12th digit is 1 (from number 11, specifically the first digit)

The challenge is to efficiently determine which digit appears at position n without generating the entire sequence up to that point. You need to figure out:

1. Which number in the sequence contains the nth digit
2. Which specific digit within that number is the answer

The approach involves recognizing that:

• 1-digit numbers (1-9) contribute 9 digits total
• 2-digit numbers (10-99) contribute 90 × 2 = 180 digits total
• 3-digit numbers (100-999) contribute 900 × 3 = 2700 digits total
• And so on...

By calculating how many digits are contributed by numbers of each length, you can determine which group contains the nth digit, then pinpoint the exact number and digit position within that number.

Intuition

Think about how digits are distributed in this infinite sequence. Instead of treating it as one long string, we can group numbers by their digit count:

• All 1-digit numbers: 1, 2, 3, ..., 9 (9 numbers, contributing 9 × 1 = 9 digits)
• All 2-digit numbers: 10, 11, 12, ..., 99 (90 numbers, contributing 90 × 2 = 180 digits)
• All 3-digit numbers: 100, 101, ..., 999 (900 numbers, contributing 900 × 3 = 2700 digits)

Notice the pattern: for k-digit numbers, there are 9 × 10^(k-1) such numbers, each contributing k digits to our sequence.

To find the nth digit, we can:

1. First determine which group (1-digit, 2-digit, 3-digit, etc.) contains our target digit
2. Then find the exact number within that group
3. Finally, identify which digit within that number

For example, if n = 195:

• First 9 digits come from 1-digit numbers (positions 1-9)
• Next 180 digits come from 2-digit numbers (positions 10-189)
• So position 195 is the 6th digit in the 3-digit group (195 - 189 = 6)
• The 6th digit in 3-digit numbers corresponds to the 2nd number (since each has 3 digits), which is 101
• Position 6 is at the last digit of 101, giving us 1

The key insight is that we don't need to generate the actual sequence. By understanding the mathematical structure of how digits are distributed across different number lengths, we can directly calculate which number contains our target digit and extract it. This reduces what could be a linear time operation to a logarithmic one based on the number of digit groups we need to check.

Solution Approach

We implement the intuition using a systematic counting approach:

Step 1: Find the digit group We iterate through groups of numbers by their digit count:

• Initialize k = 1 (starting with 1-digit numbers) and cnt = 9 (there are 9 one-digit numbers)
• While k * cnt < n, we know the nth digit is not in the current group:
  • Subtract k * cnt from n (skip all digits in this group)
  • Increment k to move to the next digit group
  • Multiply cnt by 10 (each group has 10 times more numbers than the previous)

After this loop, n has been reduced to a position within the current k-digit group, and we know our target is in a k-digit number.

Step 2: Find the exact number Within the k-digit group:

• The first k-digit number is 10^(k-1)
• Since each number contributes k digits, the number containing our target is at offset (n-1) // k from the start
• Therefore, the number is: num = 10^(k-1) + (n-1) // k

We use (n-1) instead of n because we're working with 0-based indexing for the division.

Step 3: Extract the specific digit Now we need to find which digit within num:

• The position within the number is idx = (n-1) % k
• Convert num to a string and access the character at index idx
• Convert back to integer for the final answer

Example walkthrough with n = 15:

1. Start with k=1, cnt=9. Since 1*9 = 9 < 15, subtract 9 from n (n becomes 6), increment k to 2, cnt becomes 90
2. Now k=2, cnt=90. Since 2*90 = 180 > 6, we found our group
3. The number is 10^(2-1) + (6-1)//2 = 10 + 2 = 12
4. The digit position is (6-1)%2 = 1 (second digit)
5. String "12" at index 1 gives us 2

The time complexity is O(log n) as we only iterate through digit groups, and space complexity is O(1).

Example Walkthrough

Let's find the 195th digit in the sequence 123456789101112131415...

Step 1: Find which digit group contains position 195

Start with k=1 (digit length), cnt=9 (count of 1-digit numbers), n=195

• 1-digit numbers: 1*9 = 9 digits total. Since 9 < 195, skip these.
  • Update: n = 195 - 9 = 186, k = 2, cnt = 90
• 2-digit numbers: 2*90 = 180 digits total. Since 180 < 186, skip these too.
  • Update: n = 186 - 180 = 6, k = 3, cnt = 900
• 3-digit numbers: 3*900 = 2700 digits total. Since 2700 > 6, we found our group!

Step 2: Find the exact 3-digit number

We need the 6th digit in the 3-digit number group.

• First 3-digit number: 10^(3-1) = 100
• Which number contains the 6th digit?
  • Each 3-digit number contributes 3 digits
  • Number offset: (6-1) // 3 = 5 // 3 = 1
  • The number is: 100 + 1 = 101

Step 3: Extract the specific digit from 101

Which digit of 101 do we need?

• Position within the number: (6-1) % 3 = 5 % 3 = 2
• Convert 101 to string: "101"
• Get character at index 2: "101"[2] = '1'

Answer: The 195th digit is 1

To verify: The sequence around position 195 would be ...99100101102...

• Positions 190-192: 100 (the digits 1, 0, 0)
• Positions 193-195: 101 (the digits 1, 0, 1)
• Position 195 is indeed 1 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(log₁₀ n)

The while loop iterates based on the number of digits in the sequence. In each iteration:

• k represents the number of digits (1 for single-digit numbers, 2 for double-digit numbers, etc.)
• cnt represents the count of numbers with k digits (9 single-digit numbers, 90 double-digit numbers, 900 three-digit numbers, etc.)
• The loop continues while k * cnt < n, effectively determining which digit length group contains the nth digit

Since we're dealing with base-10 numbers and each iteration increases the digit count by 1, the maximum number of iterations is proportional to the number of digits in n, which is log₁₀ n. The operations inside the loop (arithmetic operations and string conversion) are O(1) or at most O(log₁₀ num) for the string conversion, but since num is bounded by the value corresponding to position n, this doesn't exceed O(log₁₀ n).

Space Complexity: O(log₁₀ n)

The space is primarily consumed by:

• A few integer variables (k, cnt, num, idx) which take O(1) space
• The string conversion str(num) which creates a string of length equal to the number of digits in num, which is at most O(log₁₀ n)

Therefore, the overall space complexity is O(log₁₀ n).

Common Pitfalls

1. Off-by-One Errors with 1-Based vs 0-Based Indexing

The most common mistake is confusion between 1-based indexing (the problem asks for the nth digit starting from 1) and 0-based indexing (used in programming for array/string access).

Pitfall Example:

# WRONG: Forgetting to adjust for 0-based indexing
target_number = 10 ** (digit_length - 1) + n // digit_length  # Missing (n-1)
digit_index = n % digit_length  # Missing (n-1)

Why it fails: When n=11 (expecting '0' from number 10):

• Without adjustment: target_number = 10 + 11//2 = 10 + 5 = 15, digit_index = 11%2 = 1
• This gives us '5' from number 15, which is wrong!

Solution: Always use (n-1) when calculating both the target number offset and the digit index within that number, since we need to convert from 1-based to 0-based indexing.

2. Integer Overflow in Digit Count Calculation

When checking if digit_length * count < n, the multiplication can overflow for large values.

Pitfall Example:

# WRONG: Direct multiplication can overflow
while digit_length * count < n:  # Potential overflow for large values
    n -= digit_length * count

Solution: Check for potential overflow before multiplication:

while n > digit_length * count:  # Better practice
    n -= digit_length * count
    # Or use division to avoid overflow
    # while n / digit_length > count:

3. Incorrect Initial Count Value

Starting with wrong count values for different digit lengths.

Pitfall Example:

# WRONG: Starting count at 10 instead of 9
count = 10  # Should be 9 for 1-digit numbers (1-9, not 0-9)

Why it fails: This would incorrectly include 0 as a 1-digit number, throwing off all subsequent calculations.

Solution: Remember that:

• 1-digit numbers: 1-9 (count = 9)
• 2-digit numbers: 10-99 (count = 90)
• 3-digit numbers: 100-999 (count = 900)

4. Not Handling Edge Cases Properly

Failing to handle small values of n correctly.

Pitfall Example:

# WRONG: Not considering n could be in the first group
def findNthDigit(self, n: int) -> int:
    if n <= 0:  # The problem guarantees n >= 1
        return 0
    # ... rest of code

Solution: Trust the problem constraints (n >= 1) and ensure your logic works for n=1, n=9, n=10 (boundary cases between digit groups).

5. Forgetting to Convert Back to Integer

The problem asks for an integer digit, not a character.

Pitfall Example:

# WRONG: Returning a string character
return str(target_number)[digit_index]  # Returns '2' instead of 2

Solution: Always convert the final result to integer:

return int(str(target_number)[digit_index])