4.28.5 — Plus One

LeetCode 66 · Easy

The problem

A number is given as an array of digits, most significant first. Add one and return the result.

[1,2,3]     →  [1,2,4]
[4,3,2,1]   →  [4,3,2,2]
[9]         →  [1,0]
[9,9,9]     →  [1,0,0,0]

The pattern

Add one to the last digit and carry leftwards, exactly as you would on paper.

The only interesting input is all nines, because the result is one digit longer than the input. Everything else is a one-line change.

Here is the observation that makes the code short:

Walk from the right. If a digit is less than 9, add one and you are finished — there is no carry. If it is 9, set it to 0 and continue left.

The loop ends early on the first non-nine, so there is no carry variable at all.

If the loop finishes without returning, every digit was a 9. They are now all 0, and the answer is a 1 in front. That is the only case needing extra work.

The solution

Python

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1):     # right to left
            if digits[i] < 9:
                digits[i] += 1
                return digits                         # no carry — done
            digits[i] = 0                             # 9 becomes 0, carry continues

        return [1] + digits                           # every digit was 9

TypeScript

function plusOne(digits: number[]): number[] {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++;
      return digits;
    }
    digits[i] = 0;
  }

  return [1, ...digits];
}

No carry variable is needed. The early return replaces it — reaching the next iteration is the carry. That is what makes this five lines instead of ten.

[1] + digits after the loop works because every digit has already been set to 0 by then, so [9,9,9] becomes [0,0,0] and then [1,0,0,0].

Only one leading digit can ever be added, because adding 1 can never cause more than one extra digit.

Why not convert to an integer

The obvious approach is to build the number, add one, and split it back:

n = int(''.join(map(str, digits))) + 1
return [int(c) for c in str(n)]

It works in Python, where integers are unbounded. It fails in most other languages — the array can hold 100 digits, far beyond any 64-bit integer.

Say that out loud. Knowing that your language's convenience does not generalise is the point of this problem, and the array-based version is what a big-integer library actually does.

Complexity

O(n) time in the worst case — all nines. O(1) extra space when the input may be modified, or O(n) for the new array in the all-nines case.

Best case is O(1): a last digit below 9 returns immediately.

Where this goes next

• Add Two Numbers — the same carry discipline on linked lists, and there the carry variable is needed because two inputs are being combined. 4.9.6.
• Add Binary, Add Strings — same loop, different base.
• Multiply Strings — carries in two dimensions. 4.28.7.
• Big-integer arithmetic — Python's integers do this internally in base 2^{30} rather than base 10, because a bigger base means fewer digits and fewer carries. Every arbitrary-precision library is this loop.

What the interviewer will push on

"What is the interesting case?" All nines, where the result grows by one digit.

"Why is there no carry variable?" The early return replaces it; continuing the loop is the carry.

"Why not convert to an integer?" Overflow in any language with fixed-width integers, and 100 digits is far beyond 64 bits.

"What if you had to add an arbitrary number rather than 1?" Then you do need a carry variable, and the loop cannot exit early — that is Add Strings.

"Could the result ever grow by two digits?" No. Adding 1 to a number of n digits gives at most n + 1.

One thing to volunteer: name the all-nines case before writing anything, and mention that the integer conversion trick does not port to other languages. Both are one sentence and both are what the problem is testing.

Next: 4.28.6 Pow(x, n) — exponentiation in O(\log n), and a negative-number trap.