Solution For Nth Digit

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.

Step by Step Implementation For Nth Digit

public class Solution {
    public int findNthDigit(int n) {
        // edge case
        if (n < 10) return n;
        
        // find the length of the number where the nth digit is from
        // (the length of each number is 1, 2, 3, 4, ...)
        int len = 1;
        long count = 9;
        int start = 1;
        while (n > len * count) {
            n -= len * count;
            len += 1;
            count *= 10;
            start *= 10;
        }
        
        // find the actual number where the nth digit is from
        // and calculate the nth digit
        start += (n - 1) / len;
        String s = Integer.toString(start);
        return Character.getNumericValue(s.charAt((n - 1) % len));
    }
}

def findNthDigit(n: int) -> int: 
    
    # find the length of the number where the nth digit is from 
    length = 1
    while n - length * 9 * 10**(length - 1) > 0:
        n -= length * 9 * 10**(length - 1)
        length += 1
    
    # find the actual number where the nth digit is from
    num = 10**(length - 1) + (n - 1) // length
    
    # find the nth digit and return it
    return int(str(num)[(n - 1) % length])

var findNthDigit = function(n) {
    
    // create a variable to store the length of the number
    // we are looking for
    var len;
    
    // this loop will determine the length of the number
    // we are looking for
    for (len = 1; len * 9 * Math.pow(10, len - 1) < n; len++){}
    
    // create a variable to store the number we are looking for
    var num = Math.ceil((n - (len - 1) * 9 * Math.pow(10, len - 1)) / len) 
        + Math.pow(10, len - 1) - 1;
    
    // return the nth digit of that number
    return parseInt(num.toString().charAt(n % len - 1));
};

int findNthDigit(int n) {
        long base = 9, digits = 1;
        while (n - base * digits > 0) {
            n -= base * digits;
            base *= 10;
            digits++;
        }

        int index = n % digits;
        if (index == 0)
            index = digits;
        long number = 1;
        for (int i = 1; i < digits; i++)
            number *= 10;
        number += (index == digits) ? n / digits - 1 : n / digits;;

        for (int i = index; i < digits; i++)
            number /= 10;
        return number % 10;
    }

public class Solution {
    public int FindNthDigit(int n) {
        // if n is less than 10, then the nth digit is simply n
        if (n < 10)
            return n;
        
        // find the number of digits in the nth number
        int numDigits = 1;
        long num = 9;
        while (n > num * numDigits) {
            n -= num * numDigits;
            numDigits++;
            num *= 10;
        }
        
        // find the actual number the nth digit is in
        long start = (long) Math.Pow(10, numDigits - 1);
        long numN = start + (n - 1) / numDigits;
        
        // find the nth digit and return it
        return (int) ((numN / Math.Pow(10, (n - 1) % numDigits)) % 10);
    }
}