grid47 Exploring patterns and algorithms
Oct 31, 2024
5 min read
Solution to LeetCode 66: Plus One Problem
You are given a large integer represented as an array of digits. Each digits[i] represents the ith digit of the integer, arranged from most significant to least significant. The task is to increment the integer by one and return the resulting digits as an array.
Problem
Approach
Steps
Complexity
Input: An integer array digits where each element is a single digit of a number.
Example: Input: digits = [2,4,6]
Constraints:
• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits[0] != 0 (no leading zeros)
Output: Return an array representing the incremented value of the given integer.
Example: Output: [2,4,7]
Constraints:
• The output array should be of size digits.length or digits.length + 1, depending on whether a carry was generated.
Goal: Increment the integer represented by the array by one and return the resulting digits as an array.
Steps:
• Initialize a variable to handle the carry, starting with a value of 1 (representing the increment).
• Iterate over the digits array from the least significant digit to the most significant.
• Add the carry to the current digit. Update the digit to the modulo 10 of the sum, and update the carry as the integer division of the sum by 10.
• If the carry remains after the iteration, prepend it to the array.
• Return the resulting array.
Goal: The input array represents a valid non-negative integer with no leading zeros.
Steps:
• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits[0] != 0 (no leading zeros)
Assumptions:
• The input array will always represent a valid non-negative integer.
• The result will fit within the array size constraints.
• Input: Input: digits = [2,4,6]
• Explanation: The array represents the number 246. Adding one gives 246 + 1 = 247, so the output is [2,4,7].
• Input: Input: digits = [5,9,9]
• Explanation: The array represents the number 599. Adding one gives 599 + 1 = 600, so the output is [6,0,0].
Approach: Use an iterative approach starting from the least significant digit, handling any carry generated at each step. If there's a carry left after iterating through all digits, prepend it to the array.
Observations:
• The task involves managing carries as you increment the number represented by the array.
• The most significant digit might need to expand the array if a carry remains after processing all digits.
• Start with the least significant digit and propagate the carry towards the most significant digit.
Steps:
• Initialize a carry variable with the value 1 (representing the increment).
• Iterate over the digits array from right to left.
• At each step, add the carry to the current digit.
• Update the current digit to the modulo 10 of the sum and update the carry as the integer division of the sum by 10.
• If carry is still non-zero after the loop, prepend it to the array.
• Return the updated digits array.
Empty Inputs:
• Not applicable as digits.length >= 1 is guaranteed.
Large Inputs:
• A 100-digit array with the last digit causing a carry that propagates through all digits.
Special Values:
• A single-digit array [9], which becomes [1,0].
• An array with all digits being 9, such as [9,9,9], which becomes [1,0,0,0].
Constraints:
• Ensure the output correctly reflects carry propagation, even for very large arrays.
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
for (int i = n -1; i >=0; i--) {
if (digits[i] <9) {
digits[i]++;
return digits;
}
digits[i] =0;
}
// If we reach here, all digits were 9, so we need to add a new digit
vector<int> result(n +1, 0);
result[0] =1;
return result;
}
1 : Function Declaration
vector<int> plusOne(vector<int>& digits) {
This line declares a function named `plusOne` that takes a vector of digits `digits` as input and returns a vector representing the incremented number.
2 : Get Number of Digits
int n = digits.size();
This line gets the number of digits in the input number.
3 : Iterate from Rightmost Digit
for (int i = n -1; i >=0; i--) {
This loop iterates through the digits of the number from right to left.
4 : Check for Carryover
if (digits[i] <9) {
This condition checks if the current digit is less than 9. If so, it means we can simply increment it and return the result.
5 : Increment Digit
digits[i]++;
This line increments the current digit by 1.
6 : Return the Result
return digits;
This line returns the modified `digits` vector, which now represents the incremented number.
7 : Handle Carryover
digits[i] =0;
If the current digit is 9, we set it to 0 and continue to the next digit, carrying over the 1.
8 : Handle Carryover to the Leftmost Digit
// If we reach here, all digits were 9, so we need to add a new digit
vector<int> result(n +1, 0);
result[0] =1;
If we reach the end of the loop without finding a digit less than 9, it means all digits were 9. In this case, we need to create a new vector with one extra digit, set the first digit to 1, and return it.
9 : Return the Result
return result;
This line returns the newly created vector representing the incremented number.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We process each digit once, resulting in a linear time complexity.
Best Case: O(1)
Worst Case: O(n)
Description: Space is O(1) if the input can be modified in-place; otherwise, O(n) for the output array in case of carry propagation.
