grid47 Exploring patterns and algorithms
Sep 28, 2024
5 min read
Solution to LeetCode 400: Nth Digit Problem
You are given a positive integer n. Your task is to find the nth digit in an infinite sequence of consecutive integers starting from 1. The sequence starts as [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, …].
Problem
Approach
Steps
Complexity
Input: You will be given an integer n, where 1 <= n <= 2^31 - 1.
Example: For n = 12, the sequence up to the 12th digit is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], and the 12th digit is 1.
Constraints:
• 1 <= n <= 2^31 - 1
Output: Return the nth digit in the infinite sequence of consecutive integers.
Example: For n = 5, the output should be 5.
Constraints:
Goal: The goal is to identify the nth digit in the infinite sequence efficiently.
Steps:
• 1. Determine the length of the digits for the current number range.
• 2. Identify the range where the nth digit falls.
• 3. Calculate the specific number and digit within that range.
Goal: The problem operates under the constraint 1 <= n <= 2^31 - 1.
Steps:
• 1 <= n <= 2^31 - 1
Assumptions:
• The value of n is always valid and within the given constraints.
• The sequence of integers is unbounded.
• Input: For n = 12, the sequence is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. The 12th digit is part of the number 12, which is 1.
• Explanation: By breaking the sequence into ranges based on the number of digits, we can pinpoint that the 12th digit lies in the 10-99 range.
Approach: The approach is to break down the sequence into chunks of numbers with the same number of digits and locate the range containing the nth digit.
Observations:
• The sequence starts with single-digit numbers, then transitions to two-digit numbers, and so on.
• Each range of numbers contributes a different number of digits.
• We need to calculate which range the nth digit lies in and then pinpoint the exact number and digit.
Steps:
• 1. Start with single-digit numbers and calculate how many digits they contribute to the sequence.
• 2. Move to multi-digit numbers and subtract the number of digits until you locate the correct range.
• 3. Once the range is located, determine the exact number and digit.
Empty Inputs:
Large Inputs:
Special Values:
Constraints:
intfindNthDigit(int n) {
lli len =1;
lli cnt =9;
lli start =1;
while(n > len * cnt) {
n -= len * cnt;
len++;
cnt *=10;
start *=10;
}
start += (n -1) / len;
string s = to_string(start);
return s[(n -1) % len] -'0';
}
1 : Function Definition
intfindNthDigit(int n) {
Define the function `findNthDigit` that takes an integer `n` as input, which represents the position of the digit to find.
2 : Variable Initialization
lli len =1;
Initialize `len` to 1, which represents the number of digits in the current group (starting with 1-digit numbers).
3 : Variable Initialization
lli cnt =9;
Initialize `cnt` to 9, representing the number of 1-digit numbers (1 to 9).
4 : Variable Initialization
lli start =1;
Initialize `start` to 1, representing the first number in the current digit group (starting with 1).
5 : While Loop
while(n > len * cnt) {
Enter a while loop that continues until `n` is less than or equal to the total number of digits in the current group.
6 : While Loop End
End of the while loop that processes the current group of numbers based on their digit length.
7 : Update n
n -= len * cnt;
Subtract the total number of digits in the current group from `n` to shift to the next group of numbers.
8 : Increment Length
len++;
Increase the digit length `len` to move to the next group of numbers (e.g., from 1-digit to 2-digit numbers).
9 : Update Count
cnt *=10;
Multiply `cnt` by 10 to account for the next group of numbers (e.g., from 9 one-digit numbers to 90 two-digit numbers).
10 : Update Start
start *=10;
Multiply `start` by 10 to move to the first number of the next group (e.g., from 1 to 10).
11 : Find Target Digit
start += (n -1) / len;
Calculate the starting number in the group that contains the target digit.
12 : Convert to String
string s = to_string(start);
Convert the calculated starting number `start` to a string for easy indexing.
13 : Return Result
return s[(n -1) % len] -'0';
Return the digit at the target position by converting it from a character to an integer.
Best Case: O(log n)
Average Case: O(log n)
Worst Case: O(log n)
Description: The time complexity is logarithmic in terms of n, as we reduce the number of possible ranges by orders of magnitude with each iteration.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, as the solution only requires a fixed amount of space.
