Plus One
Plus One: given a large integer represented as an array of digits, most significant first, increment it by one and return the resulting digit array.
- 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 trailing nines. Walk from the last digit backwards: any digit below nine absorbs the carry and the work is finished immediately. A nine becomes zero and passes the carry left. If every digit was a nine, the number rolls over to a leading one followed by zeros.
This is manual carry propagation — the same mechanic behind 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: which digits actually change when you add one to 1299? Work out the rule for when the carry stops, and what makes the all-nines case different from every other. Aim for O(n) with no numeric conversion.
Why the number cannot simply be converted
The obvious idea is to join the digits, parse an integer, add one, and split the result. In Python that happens to work because integers are arbitrary precision, but in C++ or Java the array may represent a value far beyond 64 bits and the conversion overflows. The array representation exists precisely because the number is too large to hold natively, so the addition must be done digit by digit, exactly as it is done on paper.
Walk backwards and stop at the first digit under nine
Start at the last index. If that digit is less than nine, increment it and return the array — no other digit can change, because there is no carry to propagate. If it is nine, adding one makes ten: write zero in place and continue left with a carry. This loop naturally handles a run of trailing nines, turning [1,2,9,9] into [1,3,0,0] by zeroing two digits and then incrementing the 2. The early return matters: the common case costs one step regardless of how long the number is.
The all-nines rollover
If the loop runs off the left end, every digit was a nine and all are now zero — the value has rolled over, like 999 becoming 1000. The result needs one more digit than the input, and the answer is always a 1 followed by n zeros. Since the array already holds all zeros at that point, prepending a single 1 completes it. This is the only case where the output length differs from the input, which is why it deserves its own line rather than being folded into the loop.
Solution & live demo
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 immediately as [1,2,4].
The nine becomes zero and the carry increments the 2, giving [1,3,0].
Every digit zeroes, the loop exits, and a leading 1 is prepended for [1,0,0,0].
It becomes zero, the loop ends, and prepending gives [1,0].
No numeric conversion happens, so arbitrary length is handled without overflow.