algoadvance

LeetCode 400: Nth Digit

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Example:

Input: n = 11
Output: 0

Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is 0, which is part of the number 10.

Clarifying Questions

1. Input Constraints:
   • What is the range of n?
     • 1 <= n <= 2*10^9
2. Output:
   • The output should be a single digit from the sequence.

Strategy

1. Determine the Range:
   • Identify the range in which the nth digit falls. The sequence of digits can be broken down into segments based on number length:
     • 1 to 9 (1-digit numbers)
     • 10 to 99 (2-digit numbers)
     • 100 to 999 (3-digit numbers)
     • and so on.
2. Calculate Number Range Contribution:
   • Calculate the number of digits contributed by numbers with a specific number of digits.
   • 1-9: 9 * 1 = 9 digits
   • 10-99: 90 * 2 = 180 digits
   • 100-999: 900 * 3 = 2700 digits
   • Continue until you find the range that includes the nth digit.
3. Locate the Exact Digit:
   • After finding the correct range, calculate the exact number and the exact digit within that number where the nth digit is located.

Code

def findNthDigit(n: int) -> int:
    # Initialize the length of digits we are looking at and the count of numbers
    length = 1
    count = 9
    start = 1
    
    # While n is greater than the digits in the current range, narrow down the range
    while n > length * count:
        n -= length * count
        length += 1
        count *= 10
        start *= 10
    
    # Now n is within the current range denoted by length
    # Find the exact number where the nth digit is located
    start += (n - 1) // length
    
    # Find the exact digit within the number
    s = str(start)
    digit_index = (n - 1) % length
    return int(s[digit_index])

# Example Usage:
n = 11
print(findNthDigit(n))  # Output: 0

Time Complexity

• Time Complexity: (O(\log n))
  • The while loop runs logarithmically by increasing the length and adjusting count by powers of 10.
  • Converting a number to a string and accessing a specific character is (O(\log n)).
• Space Complexity: (O(1))
  • We use a constant amount of extra space irrespective of the input size.

This code efficiently narrows down the exact range and finds the specific digit in the continuous sequence of integers.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?