Nth Digit - Leetcode Solution

The Nth Digit problem on LeetCode asks us to find the Nth digit of the infinite sequence formed by concatenating all positive integers.

For example, if N = 11, the answer would be 0 because the 11th digit is the second digit of the number 10 (1 0).

To solve this problem, we need to break it down into smaller parts. First, we need to find the length of the number that contains the Nth digit. This can be done by figuring out how many digits the previous numbers have.

For example, if N = 11, we know that the first 9 numbers (1-9) have one digit each. The next 90 numbers (10-99) have two digits each, for a total of 180 digits. So we know that the number containing the 11th digit must have three digits.

Once we know the number of digits, we can find the actual number that contains the Nth digit. We can use integer division and modulus operators to do this.

For example, if the number containing the 11th digit has three digits, we know that it falls between 100 and 999. We can find the actual number by doing (N - 1) // 3 + 100. Here, (N - 1) // 3 gives us the number of three-digit numbers we need to skip, and we add 100 to get the actual number.

Finally, we need to find the digit itself. We can do this by using the modulus operator again to find the remainder when we divide (N - 1) by the number of digits in the number. This gives us the position of the digit in the number.

For example, if the number containing the 11th digit is 123, we know that the digit itself is the second digit in the number. We can find this by doing (N - 1) % 3, which gives us 1 (since the position of the digit is zero-indexed).

Putting it all together, the solution looks like this:

class Solution { public int findNthDigit(int n) { int digits = 1; long count = 9;

    while (n > digits * count) {
        n -= digits * count;
        digits++;
        count *= 10;
    }

    int num = (int)(Math.pow(10, digits - 1) + (n - 1) / digits);
    return Integer.toString(num).charAt((n - 1) % digits) - '0';
}

}

This solution runs in O(logN) time and O(1) space.

1