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
- 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.
- 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)). - Stop at the first digit below 9. Everything to the left of it is untouched, so
return digitscan happen immediately. - If every digit was 9, the loop ends with the whole list turned into zeros, and a new leading 1 is needed.
[1] + digitsbuilds that. - 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] + digitsIn 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
| Approach | Time | Space |
|---|---|---|
| Brute force (convert to an integer) | O(n) to O(n²) depending on the conversion, and not portable | O(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 step | O(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
digitsafter 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].
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.
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?
Borrowing mirrors carrying: trailing zeros become 9s and the first non-zero digit from the right drops by one. Converting to an integer fails for very long inputs.
2. Why does the shown code usually do far less than O(n) work?
Only a trailing run of 9s changes, so the loop ends at the first digit that is not a 9. It is O(n) only in the worst case, when all digits are 9.
3. A learner changes the last line to return digits instead of return [1] + digits. What does plus_one([9, 9]) return?
With all nines, each digit is set to 0 and the loop ends without a stop, so the list is all zeros. Running the variant gives [0, 0] where the right answer is [1, 0, 0].
Score 60% or more and the lesson is marked complete.