Plus One
Plus One is LeetCode 66 (Easy). A non-negative integer is stored as an array of digits, most significant first. Increment it by one and return the resulting digit array.
The array length runs to 100, so the value can be far beyond what a 64-bit integer holds. That is the whole reason the input is an array, and the reason the addition has to be done digit by digit.
- 1 <= digits.length <= 100
- 0 <= digits[i] <= 9
- digits does not contain any leading zeros except for the number 0 itself.
Intuition
Adding one only disturbs the tail of the number. Walk from the last digit backwards: the first digit below nine absorbs the carry, and nothing to its left can change, so the work stops there.
A nine cannot absorb it — nine plus one is ten, so the digit becomes zero and the carry moves one place left. A run of trailing nines just repeats that.
If the walk falls off the left end, every digit was a nine and all are now zero. The number has rolled over, like 999 to 1000, and the answer is a leading one in front of those zeros — the only case where the output is longer than the input.
This is carry propagation by hand, the same mechanic as Add Binary, Add Two Numbers and Multiply Strings. The tell is a number stored as digits or characters because it exceeds native integer width. Whenever you see that, resist converting and simulate the arithmetic from the least significant end.
Approach
Before reading on: work out by hand which digits of 1299 change when you add one. State the rule for where the carry stops, and what makes the all-nines case different from every other input. Aim for O(n) with no numeric conversion.
Work on the digits directly
Joining the digits and parsing an integer happens to work in Python, whose integers are unbounded, but a 100-digit value overflows long long in C++ and long in Java. The array representation exists precisely because the number does not fit, so the addition has to be simulated on paper.
Walk backwards from the last digit
Carries travel from the least significant digit towards the most significant, so the loop must run right to left. Starting at the front increments the wrong digit entirely and produces a number off by a power of ten.
Handle each digit as one of two cases
Walking right to left, each digit is one of two cases:
- Under nine: increment it and return straight away — no digit to its left can change.
- A nine: write
0in its place and carry left.
That early return is why the usual case costs one step however long the number is.
Handle the all-nines rollover after the loop
If the loop finishes without returning, every digit was a nine and the array is now all zeros. Prepend a single 1 and return. Only here does the array grow by one slot.
Plus One solution in Python | C++ | Java
3, which is under nine, so adding one fits in this position with nothing left over.9. Nine plus one is ten, which does not fit in a single digit, so this position cannot end the addition.0 here and hand the carry to position 2. A run of trailing nines just repeats this step, one digit at a time.9. Nine plus one is ten, which does not fit in a single digit, so this position cannot end the addition.0 here and hand the carry to position 1. A run of trailing nines just repeats this step, one digit at a time.2, which is under nine, so adding one fits in this position with nothing left over.9. Nine plus one is ten, which does not fit in a single digit, so this position cannot end the addition.0 here and hand the carry to position 1. A run of trailing nines just repeats this step, one digit at a time.9. Nine plus one is ten, which does not fit in a single digit, so this position cannot end the addition.0 here and hand the carry to position 0. A run of trailing nines just repeats this step, one digit at a time.9. Nine plus one is ten, which does not fit in a single digit, so this position cannot end the addition.0 here too. This was the leading digit, so there is nothing left to pass the carry to — the number has rolled over.1. This is the only input whose output is longer than its input.Common pitfalls
Converting the array to an integer
num = int(''.join(map(str, digits))) + 1
return [int(c) for c in str(num)]for i in range(len(digits) - 1, -1, -1):
...It passes in Python by accident. The array can represent a 100-digit number, which overflows a 64-bit integer in C++ or Java — and the whole reason the input is an array is that the value does not fit. The digit-wise walk ports everywhere.
Iterating forwards
for i in range(len(digits)):
for i in range(len(digits) - 1, -1, -1):
Carries propagate from the least significant digit toward the most significant, so the walk must go right to left. Starting at the front increments the wrong digit entirely.
Forgetting the all-nines case
for i in ...:
...
digits[i] = 0
# no return after the loopreturn [1] + digits
When every digit is a nine the loop finishes without returning, and the function falls through to None (or returns an all-zero array). [9,9] must become [1,0,0] — the only input whose output is longer.
Edge cases
The last digit is under nine, so it increments and returns straight away as [1,2,4].
Both nines become zero and the carry stops at the 2, giving [1,3,0,0].
All digits zero, the loop runs off the end, and a leading 1 is prepended for [1,0,0,0] — the only output longer than its input.
Nothing is ever converted to a native integer, so the length is irrelevant and no overflow is possible.