Solution Explanation: Finding the Nth Digit

This problem asks to find the nth digit in the infinite sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... A naive approach of iterating through the sequence until the nth digit is found would be highly inefficient. Instead, we use a mathematical approach to solve this efficiently.

Mathematical Approach

The core idea is to determine the length of the numbers (number of digits) that contain the nth digit. We can then identify the specific number and digit within that number.

1. Grouping by Digit Length: The sequence can be divided into groups based on the number of digits.

   • 1-digit numbers (1-9): 9 numbers, 9 digits total.
   • 2-digit numbers (10-99): 90 numbers, 180 digits total.
   • 3-digit numbers (100-999): 900 numbers, 2700 digits total.
   • and so on...

2. Finding the Relevant Group: We iteratively check which group contains the nth digit. We start with 1-digit numbers, then 2-digit, 3-digit, and so on. We keep track of the cumulative number of digits (cnt) across groups. As soon as the cumulative count (cnt) exceeds or equals n, we've found the group containing the nth digit.

3. Identifying the Number and Digit:

   • Once we know the group, we can determine the number (num) containing the nth digit.
   • We calculate the index (idx) of the digit within that number.

Time Complexity Analysis:

The loop iterating through the digit lengths (1, 2, 3, ...) runs at most log₁₀(n) times. This is because the number of digits in the number containing the nth digit is roughly proportional to log₁₀(n). All other operations within the loop are constant time. Therefore, the overall time complexity is O(log₁₀(n)), which is very efficient.

Space Complexity Analysis:

The space complexity is O(1) because we use only a constant number of variables to store intermediate values.

Code Examples

The following code examples demonstrate the solution in various programming languages. They all follow the same mathematical approach explained above.

Python

class Solution:
    def findNthDigit(self, n: int) -> int:
        k, cnt = 1, 9
        while k * cnt < n:
            n -= k * cnt
            k += 1
            cnt *= 10
        num = 10 ** (k - 1) + (n - 1) // k
        idx = (n - 1) % k
        return int(str(num)[idx])

Java

class Solution {
    public int findNthDigit(int n) {
        int k = 1, cnt = 9;
        while ((long) k * cnt < n) {
            n -= k * cnt;
            ++k;
            cnt *= 10;
        }
        int num = (int) Math.pow(10, k - 1) + (n - 1) / k;
        int idx = (n - 1) % k;
        return String.valueOf(num).charAt(idx) - '0';
    }
}

C++

class Solution {
public:
    int findNthDigit(int n) {
        long long k = 1, cnt = 9;
        while (k * cnt < n) {
            n -= k * cnt;
            ++k;
            cnt *= 10;
        }
        long long num = pow(10, k - 1) + (n - 1) / k;
        int idx = (n - 1) % k;
        return to_string(num)[idx] - '0';
    }
};

Go

func findNthDigit(n int) int {
	k, cnt := 1, 9
	for (k * cnt) < n {
		n -= (k * cnt)
		k++
		cnt *= 10
	}
	num := int(math.Pow10(k-1)) + (n-1)/k
	idx := (n - 1) % k
	return int(strconv.Itoa(num)[idx] - '0')
}

JavaScript

var findNthDigit = function(n) {
    let k = 1, cnt = 9;
    while (k * cnt < n) {
        n -= k * cnt;
        k++;
        cnt *= 10;
    }
    let num = Math.pow(10, k - 1) + Math.floor((n - 1) / k);
    let idx = (n - 1) % k;
    return parseInt(String(num)[idx]);
};

C#

public class Solution {
    public int FindNthDigit(int n) {
        long k = 1, cnt = 9;
        while (k * cnt < n) {
            n -= (int)(k * cnt);
            k++;
            cnt *= 10;
        }
        long num = (long)Math.Pow(10, k - 1) + (n - 1) / k;
        int idx = (n - 1) % (int)k;
        return int.Parse(num.ToString()[idx].ToString());
    }
}

These code examples efficiently solve the problem by leveraging the mathematical properties of the digit sequence, achieving a logarithmic time complexity. Note that type handling (e.g., long long in C++) might be necessary to prevent integer overflow for large values of n.