algoadvance

Leetcode 400. Nth Digit

Problem Statement

The problem is to find the Nth digit of the infinite sequence of positive integers “123456789101112131415161718192021…”. The sequence is formed by concatenating the positive integers consecutively.

Clarifying Questions

  1. Input Bounds: What is the range of possible values for n?
    • The constraints are (1 \leq n \leq 2^{31} - 1).
  2. Output: Should the output be the actual digit represented as an integer?
    • Yes, the output should be a single digit (0-9) as an integer.

Strategy

To determine the Nth digit in this sequence, we can break down the sequence into segments based on the number of digits in the numbers:

  1. 1-digit numbers: There are 9 numbers (1 to 9).
  2. 2-digit numbers: There are 90 numbers (10 to 99).
  3. 3-digit numbers: There are 900 numbers (100 to 999).
  4. k-digit numbers: There are (9 \times 10^{(k-1)}) numbers.

Steps:

  1. Determine the range in which the Nth digit falls.
  2. Calculate the exact number and its corresponding digit.

Detailed Steps and Code

  1. Initialize the length of the current range of numbers and the count of total digits calculated so far.
  2. Loop through ranges of increasing digit lengths (1-digit, 2-digit, etc.), adjusting n accordingly.
  3. Determine the actual number in the sequence and extract the Nth digit.
public int findNthDigit(int n) {
    if (n < 10) return n;

    int digitLength = 1;
    long count = 9;
    int start = 1;

    // Determine the digit length and starting number of the range containing the nth digit
    while (n > digitLength * count) {
        n -= digitLength * count;
        digitLength++;
        count *= 10;
        start *= 10;
    }

    // Determine the actual number within the range
    start += (n - 1) / digitLength;

    // Determine the index of the digit in the final number
    String number = Integer.toString(start);
    int digitIndex = (n - 1) % digitLength;

    // Return the digit
    return number.charAt(digitIndex) - '0';
}

Time Complexity

The time complexity of this solution is O(log n) due to the while loop, which effectively reduces the value of n by a significant factor each iteration. The operations inside the loop (digit calculations and string operations) are constant time and less impactful.

Explanation

  1. Initialization: We start with the count of digits in 1-digit numbers.
  2. Loop: We adjust n down while skipping entire ranges of numbers until we identify the range that contains the Nth digit.
  3. Calculation: Once the range is identified, we calculate the exact number and then the specific digit within that number.

This strategy ensures that we efficiently find the Nth digit without constructing the huge sequence.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI