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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Nth Digit

Number: 400

Difficulty: Medium

Paid? No

Companies: Google, Accenture, Microsoft, Bloomberg, Apple

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, ...]. For example, when n = 11, the output is 0 because the 11th digit corresponds to the digit 0 in the number 10.

Key Insights

  • The infinite sequence can be split into groups based on the number of digits (1-digit, 2-digit, etc.).
  • Calculate the total number of digits in each group to determine where the nth digit falls.
  • Once the correct group is identified, compute the exact number and then the specific digit within that number.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

We first determine the group (digit length) where the nth digit lies by subtracting the count of digits in each group (for 1-digit numbers, 2-digit numbers, etc.) from n until n is small enough to be within a particular group. Once the group is identified, we compute the starting number of that group (10^(digitLength - 1)). We then calculate the exact number that contains the nth digit using the offset (n-1) / digitLength, and finally find the required digit using modulo (n-1) % digitLength. This approach is efficient as it iterates through groups logarithmically with respect to n and uses only constant space.

Code Solutions

def findNthDigit(n):
    # Initialize digit length for current group (starting with 1-digit numbers)
    digit_length = 1
    count = 9 * digit_length * (10 ** (digit_length - 1))
    # Loop until n is within the current digit length group
    while n > count:
        n -= count
        digit_length += 1
        count = 9 * digit_length * (10 ** (digit_length - 1))
    # Determine the actual number where nth digit lies
    start = 10 ** (digit_length - 1)
    # Calculate the number offset in the current group
    number = start + (n - 1) // digit_length
    # Determine the index of the digit in this number
    digit_index = (n - 1) % digit_length
    return int(str(number)[digit_index])

# Example usage:
print(findNthDigit(3))   # Expected output: 3
print(findNthDigit(11))  # Expected output: 0
← Back to All Questions