400. Nth Digit

Description

The problem is to find the Nth digit in an infinite sequence of numbers, where all numbers are concatenated in order. For example, for n = 11, the sequence would look like 123456789101112..., and the 11th digit is 0 from 10.

Given an integer n, the goal is to return the Nth digit of the sequence.

Intuition

The numbers are concatenated together into an infinite string. The key observation is that numbers have different lengths:

• Single-digit numbers: 1 to 9 (9 digits).
• Two-digit numbers: 10 to 99 (180 digits).
• Three-digit numbers: 100 to 999 (2700 digits).

The idea is to determine which range the nth digit belongs to by adjusting the value of n. Once we find the range, we compute the exact number that contains the Nth digit and return the digit.

Approach

1. Initialize the variables to represent: - digitInNum: the current number of digits in the range. - start: the starting number of the current range. - end: the total number of digits in the current range.
2. Traverse through the number ranges: - For each range of digits, check if n can be found within that range. - Subtract the number of digits in the current range from n and move to the next range. - Continue until n falls into a specific range.
3. Once the range is found, calculate which number contains the Nth digit: - Use (n-1) / digitInNum to determine the exact number. - Convert the number to a string and return the correct digit using (n-1) % digitInNum.

Complexity

Time Complexity:

O(log n). The while loop reduces n based on the number of digits in the range. Since the number of digits increases exponentially, the loop runs in logarithmic time relative to n.

Space Complexity:

O(1). We only use a few variables to track the state of the problem.

Code

C++

class Solution {
public:
    int findNthDigit(int n) {
        long digitInNum = 1, start = 1, end = 9;

        while (n > digitInNum * end) {
            n -= digitInNum * end;
            digitInNum++;
            start *= 10;
            end *= 10;
        }

        long num = start + (n - 1) / digitInNum;
        string numStr = to_string(num);
        return numStr[(n - 1) % digitInNum] - '0';
    }
};

Python

class Solution:
    def findNthDigit(self, n: int) -> int:
        digit_in_num = 1
        start = 1
        end = 9

        while n > digit_in_num * end:
            n -= digit_in_num * end
            digit_in_num += 1
            start *= 10
            end *= 10

        num = start + (n - 1) // digit_in_num
        return int(str(num)[(n - 1) % digit_in_num])

Java

class Solution {
    public int findNthDigit(int n) {
        long digitInNum = 1, start = 1, end = 9;

        while (n > digitInNum * end) {
            n -= digitInNum * end;
            digitInNum++;
            start *= 10;
            end *= 10;
        }

        long num = start + (n - 1) / digitInNum;
        String numStr = Long.toString(num);
        return numStr.charAt((int) ((n - 1) % digitInNum)) - '0';
    }
}

JavaScript

var findNthDigit = function (n) {
    let digitInNum = 1;
    let start = 1;
    let end = 9;

    while (n > (digitInNum * end)) {
        n = n - digitInNum * end;
        digitInNum++;
        start = start * 10;
        end = end * 10;
    }

    let num = start + Math.floor((n - 1) / digitInNum);
    num = num.toString();
    return num[(n - 1) % digitInNum];
};