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:

Input: n = 3
Output: 3

Example 2:

Input: n = 11
Output: 0
Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.

Constraints:

• $1<=n<=2^{31}-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
}

原文地址：https://blog.csdn.net/navicheung/article/details/142750170

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！