Plus One
Understanding the Problem
We have a number split across an array, one digit per slot, with the most significant digit at index 0. We add 1 to this number and return the updated array. For most inputs this is a single step: increment the last digit.
The complication starts when the last digit is 9. Adding 1 to 9 gives 10, so we set that digit to 0 and carry 1 to the next position. If that next position is also 9, the carry continues. The boundary case is a number like 999: adding 1 gives 1000, which needs a longer array than the input.
The core of the problem is propagating the carry correctly. We only keep carrying while the current digit is 9. Once we reach a digit below 9, we increment it and stop, since incrementing a digit below 9 produces no further carry.
Key Constraints:
1 <= digits.length <= 100→ The array can hold up to 100 digits, representing a number far beyond what a 64-bit integer can hold (which tops out around 19 digits). This rules out converting to a number, adding 1, and converting back.0 <= digits[i] <= 9→ Each element is a single digit. After adding 1, any digit that reaches 10 rolls over to 0 with a carry.No leading zeroes→ The input is well-formed. The output might still need an extra leading digit (999 becomes 1000).
Approach 1: Carry Simulation (Full Loop)
Intuition
Simulate grade-school addition. Start from the last digit, add 1 (or the running carry), and propagate left. We hold a carry variable and process every digit from right to left.
This version processes every digit regardless of whether the carry has already resolved. It maps directly onto how addition works on paper, which makes it hard to get wrong.
Algorithm
- Initialize
carry = 1(since we're adding one). - Loop from the last digit to the first.
- At each position, compute
sum = digits[i] + carry. - Set
digits[i] = sum % 10(the digit to keep). - Set
carry = sum / 10(the carry for the next position). - After the loop, if
carryis still 1, create a new array of sizen + 1, set the first element to 1, and return it.
Example Walkthrough
Code
- Time Complexity: O(n). We always iterate through all n digits, even if the carry resolves after the first step.
- Space Complexity: O(1) amortized, O(n) worst case. We modify the input in place. Only when all digits are 9 do we allocate a new array.
This version always touches every digit. The next approach stops as soon as the carry resolves.
Approach 2: Early Return (Optimal)
Intuition
The carry is always either 0 or 1, since the largest single-digit sum is 9 + 1 = 10. When we add 1 to a digit below 9, the result is at most 9, so there is no carry to propagate and we can return right away.
So we only continue past a digit when it equals 9. In that case it becomes 0 and the carry moves left to the next digit. If the loop runs off the front of the array without returning, every digit was 9, and the answer is a new array of length n + 1 that starts with 1 followed by all zeroes.
Algorithm
- Loop from the last digit to the first.
- If
digits[i] < 9, increment it by 1 and return the array immediately. - If
digits[i] == 9, set it to 0 and continue to the next digit (carry propagates). - If the loop finishes without returning, all digits were 9. Create a new array of size
n + 1, set the first element to 1, and return it.
Example Walkthrough
Code
- Time Complexity: O(n) worst case, O(1) best case. Worst case: all digits are 9, we process all n digits. Best case: the last digit is not 9, we return after one step.
- Space Complexity: O(1) amortized, O(n) worst case. We modify the input in place. Only when all digits are 9 do we allocate a new array.