We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Nth Digit

Difficulty: Medium

Problem Description

Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Key Insights

  • The sequence of numbers is continuous and increases indefinitely.
  • The numbers can be categorized by their digit lengths (1-digit, 2-digit, etc.).
  • To find the nth digit, we need to determine which number and which digit within that number corresponds to n.
  • The total number of digits contributed by each range of digit lengths can be calculated.

Space and Time Complexity

Time Complexity: O(log n) - We only loop through the number of digit lengths until we find the range where n falls. Space Complexity: O(1) - We are using a constant amount of extra space.

Solution

To solve the problem, we can break it down into the following steps:

  1. Determine the digit length of the numbers we are considering (1-digit, 2-digit, etc.).
  2. Calculate how many digits are contributed by each group of numbers until we find the group that contains the nth digit.
  3. Identify the exact number and the specific digit within that number.

We will use a loop to find the range of digit lengths and keep track of the total digits counted. Once we know the range, we can determine the specific number and its digit using simple arithmetic.

Code Solutions

def findNthDigit(n: int) -> int:
    digit_length = 1  # Current digit length
    count = 9         # Count of numbers with the current digit length
    start = 1         # Starting number with the current digit length

    # Determine the range in which n falls
    while n > digit_length * count:
        n -= digit_length * count
        digit_length += 1
        count *= 10
        start *= 10

    # Find the actual number that contains the nth digit
    start += (n - 1) // digit_length
    number_str = str(start)
    
    # Find the specific digit
    return int(number_str[(n - 1) % digit_length])
← Back to All Questions