LeetCode //C - 400. Nth Digit

400. Nth Digit

Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …].
 

Example 1:

Example 2:

Constraints:

• 1 < = n < = 2 31 − 1 1 <= n <= 2^{31} - 1 1<=n<=231−1

From: LeetCode
Link: 400. Nth Digit

---

Solution:

Ideas:

1. Step 1: Range identification

• The loop in findNthDigit reduces n by the number of digits in ranges of numbers (1-digit, 2-digits, 3-digits, etc.).

2. Step 2: Find the exact number

• After identifying the correct range, the exact number containing the nth digit is calculated using range_start + (n - 1) / digit_count.

3. Step 3: Extract the digit

• The number is converted to a string, and the required digit is accessed via the character array.

Code:

int findNthDigit(int n) {
    // Step 1: Determine the range the nth digit falls into
    long long digit_count = 1;  // Number of digits in the current range (1-digit, 2-digits, etc.)
    long long range_start = 1;  // First number in the current range (1, 10, 100, ...)
    long long numbers_in_range = 9; // Numbers in the current range (9 for 1-digit numbers, 90 for 2-digit numbers, ...)
    
    // Reduce n to find the range of the nth digit
    while (n > digit_count * numbers_in_range) {
        n -= digit_count * numbers_in_range; // Subtract the number of digits in the current range
        digit_count++;                       // Increase to the next range (1-digit -> 2-digit -> 3-digit, etc.)
        range_start *= 10;                   // Start of the next range (1 -> 10 -> 100, etc.)
        numbers_in_range *= 10;              // Number of numbers in the next range (9 -> 90 -> 900, etc.)
    }
    
    // Step 2: Find the exact number containing the nth digit
    long long number = range_start + (n - 1) / digit_count; // The exact number
    int digit_index = (n - 1) % digit_count;                // The position of the digit in the number
    
    // Step 3: Extract the digit from the number
    char number_str[20];                                    // Buffer to hold the number as a string
    sprintf(number_str, "%lld", number);                    // Convert the number to a string
    return number_str[digit_index] - '0';                   // Return the digit as an integer
}