Plus One

Q: What is the time complexity of Plus One?

Both approaches run in O(n) time for n digits, because the worst case, all 9s, touches every digit. The early-exit version stops after the trailing 9s, so for a number that ends in a digit below 9 it does one step. It uses O(1) extra space, except when the answer needs a new leading digit.

Q: When does the result have more digits than the input?

Only when every digit is 9. Then the number is 10^n - 1 , and adding one gives 10^n : a 1 followed by n zeros. If any digit is below 9, it absorbs the carry, so the length stays the same.

EasyMath and simulation

+10

A non-negative whole number is stored as an array of its decimal digits, digits, most significant digit first: 472 is [4, 7, 2]. Add one to the number and return the digits of the result in the same form. The number can have up to 100 digits, far more than a 64-bit integer holds.

Function

plusOne(digits: integer-array) → integer-array

digitsinteger-array: the digits of the number, most significant first
Returnsinteger-array: the digits of the number plus one, most significant first

Constraints

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits has no leading zero, except for the number 0 itself, which is [0].

Examples

Input: digits = [4, 3, 9]
Output: [4, 4, 0]
Explanation: The number is 439, and 439 + 1 = 440. The last digit 9 turns into 0 and passes a carry to the 3, which becomes 4.

Input: digits = [0]
Output: [1]
Explanation: The number 0 is written as [0], and 0 + 1 = 1.

+13 hidden tests on Submit

Follow-up

How would you subtract one instead, for a number of at least 1? Which digits change, and when does the result lose its leading digit, as in [1, 0, 0]?

Solution

Converting the digits to a number, adding one and converting back fails here: 100 digits overflow every 64-bit integer, which stops near 1.8 × 10^19. So you add the way you do on paper, from the last digit with a carry. The one observation that shortens the work: adding 1 changes only the trailing 9s, which become 0s, and the first digit to their left. Every other digit stays as it is.

Add with a carry, digit by digit

Intuition

Write the number down and add 1 under its last digit, as in school. Start with a carry of 1, the one you are adding. At each digit from the right, the column total is the digit plus the carry. Its last digit, total % 10, goes into the answer, and its tens digit, total / 10, is the carry for the next column.

With a carry of 1, a column total is at most 9 + 1 = 10, so the carry is always 0 or 1. If a carry is still left after the first digit, the answer gains a new leading digit: 999 + 1 needs a fourth place for the 1 of 1000.

The answer comes out last digit first, because that is the order you compute it in. Collect it that way and reverse it at the end. This costs O(n) time and a new array of up to n + 1 digits.

Algorithm

Set carry to 1 and start an empty list for the answer.
For each digit from the last to the first, compute total = digit + carry.
Append total % 10 to the answer and set carry to total / 10, rounded down.
After the loop, if carry is 1, append it.
Reverse the answer and return it.

def plusOne(digits):
    result = []  # the answer, last digit first
    carry = 1  # the one you are adding
    for i in range(len(digits) - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    if carry > 0:
        result.append(carry)
    result.reverse()
    return result

Stop at the first digit below 9

Intuition

Watch what the carry does when you add exactly 1. A digit below 9 absorbs it: 3 becomes 4, the carry becomes 0, and every digit further left keeps its value. Only a 9 passes the carry on, by turning into 0. So adding 1 means: turn the trailing 9s into 0s, then add 1 to the digit right before them.

Walk from the last digit to the left. On a 9, write 0 and keep going. On any other digit, increase it by one and return the array right away, since nothing to its left can change. For [2, 9, 0, 9] the last 9 becomes 0, the 0 becomes 1, and you stop with [2, 9, 1, 0] without looking at the first two digits.

If the loop never finds a digit below 9, every digit was 9 and is now 0. The number was 10^n - 1, so the answer is a 1 followed by n zeros. That is the only case that needs a new array. Everywhere else you change the input in place, so the extra space is O(1), and the loop runs once per trailing 9 plus one more step.

Algorithm

Walk the indices from the last to the first.
If the digit is below 9, increase it by one and return the array.
Otherwise the digit is 9: set it to 0 and move one place left.
If the loop ends, every digit was 9: return 1 followed by the n zeros.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1  # no carry leaves this digit, so the rest stays as it is
            return digits
        digits[i] = 0  # 9 + 1 = 10: write 0 and carry one to the left
    # Every digit was 9: the answer is 1 followed by zeros.
    return [1] + digits

Pitfalls and edge cases

The traps are integer overflow and the all-9s case.

Turning the array into an integer and back. It passes small tests, then fails on the 100-digit ones: a 64-bit integer holds at most 19 or 20 digits, and a floating-point number loses the last digits even sooner.
Forgetting the extra digit. [9, 9, 9] must become [1, 0, 0, 0], four digits. Code that only rewrites the existing places returns [0, 0, 0].
Adding 1 to the first digit instead of the last. The array is most significant first, so the units digit sits at the end.
Forgetting to return after a digit below 9 absorbs the carry. In the early-exit version the loop goes on and changes digits that must stay as they are. In [1, 9, 3] only the 3 may change; the answer is [1, 9, 4].
Mixing up the index order in Lua and R, where arrays start at 1: the last digit is at index n, and a new leading 1 goes in front of index 1.

Frequently asked questions4

What is the time complexity of Plus One?

Both approaches run in O(n) time for n digits, because the worst case, all 9s, touches every digit. The early-exit version stops after the trailing 9s, so for a number that ends in a digit below 9 it does one step. It uses O(1) extra space, except when the answer needs a new leading digit.

Why not convert the digits to an integer?

Because the number can have 100 digits and a 64-bit integer stops at about 1.8 × 10^19, which is 20 digits. Python and Ruby have unlimited integers, so the conversion works there, but it hides the point of the exercise and does not carry over to other languages. Working digit by digit never overflows.

When does the result have more digits than the input?

Only when every digit is 9. Then the number is 10^n - 1, and adding one gives 10^n: a 1 followed by n zeros. If any digit is below 9, it absorbs the carry, so the length stays the same.

How do you add two numbers stored as digit arrays?

Use the column method from the first approach with two indices, one at the end of each array. Each column adds the two digits, treating a missing digit as 0, plus the carry. Keep going until both arrays are used up and the carry is 0, then reverse the collected digits.

Python

def plusOne(digits):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

digits = [4, 3, 9]

Expected

[4, 4, 0]