LeetCode 66 · Math & Geometry

Plus One, explained with a picture

A car odometer rolling over.

EasyMath & Geometry
▶ Watch it step by step

The problem

A large number is given as a list of digits. Add one and return the new list of digits.

Input:  [1, 2, 9, 9]
Output: [1, 3, 0, 0]

Picture it

Picture a car odometer. Add one to the last wheel. A 9 rolls over to 0 and pushes a carry to the wheel on its left; any other digit just goes up by one and we stop. If every wheel was 9, a new 1 appears on the far left.

How to recognise it

  • A number is stored as a list of digits, too long (or too inconvenient) to hold as one integer.
  • You do elementary arithmetic on it: adding one, with carries moving left.
  • The most significant digit is first, so you work from the end of the list.
  • Only one of two things can happen at each digit: it goes up by one and you stop, or it was a 9 and the carry continues.
  • Sizes are small (up to 100 digits), so the lesson is about handling the carry correctly.

Start with brute force

Glue the digits into one integer, add one, and split the result back into digits.

def plus_one_brute(digits):
    n = int("".join(map(str, digits))) + 1
    return [int(ch) for ch in str(n)]

In Python this works for 100 digits and is correct. The weakness is that it does not scale: in languages with fixed-size integers a 100-digit number overflows (a 64-bit integer holds about 19 digits). Even in Python, recent versions refuse to turn a string of more than 4300 digits into an integer by default (a ValueError), so the idea does not scale to very long inputs. Time is O(n) to O(n²) depending on the conversion cost, and space is O(n).

From brute force to the idea

  1. Do it like on paper. Adding one starts at the last digit. If it is below 9, add one and you are done: nothing else changes.
  2. If it is a 9, it becomes 0 and a carry of one moves to the digit on its left. The loop goes from the last index down to 0 (range(len(digits) - 1, -1, -1)).
  3. Stop at the first digit below 9. Everything to the left of it is untouched, so return digits can happen immediately.
  4. If every digit was 9, the loop ends with the whole list turned into zeros, and a new leading 1 is needed. [1] + digits builds that.
  5. Note the side effect. The function edits the list it receives and returns it, except in the all-9s case, where it returns a new, longer list.

This is the key idea: only a run of 9s at the end can change, so walk from the right and stop at the first digit that is not a 9.

The key idea

Walk from the right, turning 9s into 0s until a digit can be incremented. O(n).

Python solution

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0               # 9 rolls over to 0, carry on
    return [1] + digits

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (convert to an integer)O(n) to O(n²) depending on the conversion, and not portableO(n): the integer and the new list
Walk from the right (shown code)O(n) in the worst case (all 9s); usually stops after one stepO(1) extra, except the new list of n + 1 digits when all are 9

Edge cases

  • No 9 at the end ([1, 2, 3]): returns [1, 2, 4], after one step.
  • A carry through the middle ([1, 2, 9, 9]): returns [1, 3, 0, 0].
  • A 9 only inside ([1, 9, 3]): the last digit is 3, so only it changes.
  • All nines ([9, 9, 9]): returns [1, 0, 0, 0], one digit longer.
  • A single 9 or a single 0 ([9], [0]): returns [1, 0] and [1].
  • Side effect: the function changes the input list. After plus_one([9, 9]), the argument has become [0, 0] while the result is a new list [1, 0, 0]. An empty list would return [1], but the problem promises at least one digit.

Common mistakes

  • Returning digits after the loop in the all-9s case, which gives [0, 0] instead of [1, 0, 0] (see the quiz).
  • Not stopping at the first digit below 9, so every digit gets +1 ([1, 2, 3] becomes [2, 3, 4]).
  • Only adding one to the last digit, so [1, 2, 9] becomes [1, 2, 10].
Your turn: least significant digit first

The digits are stored in reverse order, with the least significant digit first, as in a linked list: 129 is [9, 2, 1]. Add one. For [9, 9] (the number 99) the answer is [0, 0, 1]. Describe your approach, then write it if you like.

Compare with our answer

The carry now moves to the right, so walk from the front of the list. The all-9s case appends the new digit at the end instead of the start.

def plus_one_reversed(digits):
    for i in range(len(digits)):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return digits + [1]

plus_one_reversed([9, 9]) is [0, 0, 1], [3, 2, 1] becomes [4, 2, 1], and [9, 0, 1] becomes [0, 1, 1]. Time O(n), space O(1) extra.

A strong answer mentions: starting at index 0, stopping at the first digit below 9, and appending the final carry at the end.

Check what stuck

1. A number is given as a list of digits (most significant first) and you must subtract one from it (the number is at least 1). Which approach fits best?

2. Why does the shown code usually do far less than O(n) work?

3. A learner changes the last line to return digits instead of return [1] + digits. What does plus_one([9, 9]) return?

Score 60% or more and the lesson is marked complete.