Plus One

Q: What is the time complexity of Plus One?

Both approaches run in O(n) time for n digits, because the all-9s case touches every digit. The early-exit version stops after the trailing 9s and uses O(1) extra space, except when the answer needs a new leading digit.

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.

Follow-up

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

Solution

A 100-digit number overflows every 64-bit integer, which stops near 1.8 × 10^19, so you cannot convert and add. Add the way you do on paper, from the last digit with a carry. Adding 1 changes only the trailing 9s, which become 0s, and the digit to their left.

Add with a carry, digit by digit

Intuition

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: total % 10 goes into the answer and total / 10 is the next carry. A total is at most 9 + 1 = 10, so the carry stays 0 or 1. A carry left over after the first digit becomes a new leading digit, as in 999 + 1 = 1000.

You produce the answer last digit first, so collect it that way and reverse it at the end. That is 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

A digit below 9 absorbs a carry of 1: it grows by one and every digit to its left keeps its value. Only a 9 passes the carry on, by turning into 0. So you can stop at the first digit below 9 and return the input array, changed in place. For [2, 9, 0, 9] the last 9 becomes 0, the 0 becomes 1, and you return [2, 9, 1, 0] without reading the first two digits.

If no digit is below 9, the number was 10^n - 1 and the answer is 1 followed by n zeros. That is the only case that needs a new array, so the extra space is otherwise O(1).

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

Turning the array into an integer and back. A 64-bit integer holds at most 19 or 20 digits, so 100 digits overflow, and a floating-point number loses the last digits even sooner.
Forgetting the extra digit. [9, 9, 9] must become [1, 0, 0, 0]; code that only rewrites the existing places returns [0, 0, 0].
Adding 1 to the first digit. The array is most significant first, so the units digit is the last element.
Not returning once a digit below 9 absorbs the carry. The loop then changes digits that must stay: [1, 9, 3] must become [1, 9, 4].
In Lua and R, arrays start at 1, so the last digit is at index n, not n - 1.

Frequently asked questions3

What is the time complexity of Plus One?

Both approaches run in O(n) time for n digits, because the all-9s case touches every digit. The early-exit version stops after the trailing 9s and uses O(1) extra space, except when the answer needs a new leading digit.

Why not convert the digits to an integer?

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 the code does not carry over to other languages. Working digit by digit never overflows.

How do you add two numbers stored as digit arrays?

Use the column method with one index at the end of each array. Each column adds the two digits, treating a missing digit as 0, plus the carry. Stop when both arrays are used up and the carry is 0, then reverse the collected digits.

def plusOne(digits):
    # Write code here

Test #1

Test #2

Test #3

Argument

digits = [4, 3, 9]

Expected Output

[4, 4, 0]