LeetCode 400: Nth Digit Solution

Problem Explanation

Explanation

To solve this problem, we need to find the digit at the nth position in the infinite sequence of integers [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]. The key idea is to first determine the range of numbers where the nth digit lies and then find the specific digit within that number.

Calculate the number of digits in each range of numbers: 1-9, 10-99, 100-999, and so on.
Find the range where the nth digit is located by subtracting the number of digits in each range from n until we find the correct range.
Determine the actual number where the nth digit is located within the range.
Find the specific digit at the nth position within that number.

The time complexity of this algorithm is O(log n) as we are iterating through the digits in the number ranges, and the space complexity is O(1) as we are using constant space.

Solution Code

class Solution {
    public int findNthDigit(int n) {
        int len = 1; 
        long count = 9;
        int start = 1;
        
        while (n > len * count) {
            n -= len * count;
            len++;
            count *= 10;
            start *= 10;
        }
        
        start += (n - 1) / len;
        String s = Integer.toString(start);
        return Character.getNumericValue(s.charAt((n - 1) % len));
    }
}

Frequently Asked Questions

How to solve LeetCode 400 (Nth Digit)?

This page provides optimized solutions for LeetCode problem 400 (Nth Digit) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 400 (Nth Digit)?

The time complexity for LeetCode 400 (Nth Digit) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 400 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 400 in Java, C++, or Python.

400. Nth Digit