Plus One

Plus One looks trivial — add 1 to a number — but the number is stored as an array of digits, so you have to handle carrying by hand. It is a clean lesson in simulating grade-school addition.

The slow way first

The tempting shortcut: join the digits into a string, convert to an integer, add 1, then split it back into digits. That works for small inputs, but the whole reason the number is given as an array is that it can be bigger than any built-in integer type can hold. Converting defeats the purpose, and in languages without arbitrary-precision ints it overflows.

The question to ask: how do I add 1 by hand? I start at the rightmost digit and carry leftward only as far as I need to.

The idea: carry from the right

Walk the digits right to left. At each digit:

• If it is 9, adding 1 turns it into 10, so write 0 and carry to the next digit left.
• If it is anything else, just add 1 — there is no more carry, so return immediately.

If you fall off the left end still carrying (the number was all 9s, like 999), prepend a 1.

The key insight: a carry only travels through a run of trailing 9s. The moment we hit a non-9 digit, we are done — most of the time after touching just one digit.

Walk through it

Step through the animation. The pointer i starts at the rightmost digit and moves left. The trailing 9 becomes 0 and carries; the 2 becomes 3 with no carry, so we stop and return [1, 3, 0].

Pseudocode

i = last index of digits
while i is a valid index:
    if digits[i] is 9:
        set digits[i] to 0      # carry to the left
        move i one step left
    else:
        add 1 to digits[i]      # no carry needed
        return digits
return [1] + digits             # all digits were 9, prepend a new 1

The Python solution

def plus_one(digits):
    i = len(digits) - 1
    while i >= 0:
        if digits[i] == 9:
            digits[i] = 0
            i -= 1
        else:
            digits[i] += 1
            return digits
    return [1] + digits

• i starts at the last index so we add from the least significant digit.
• The while loop only keeps running while we are still carrying through 9s.
• A 9 becomes 0 and we step left — the carry rolls on.
• The first non-9 digit gets += 1 and we return right away; no need to touch the rest.
• If the loop runs off the left end, every digit was a 9, so we prepend a fresh 1 (e.g. [9, 9] → [1, 0, 0]).

Complexity

We modify the array in place, so no extra space beyond the output — and only in the all-9s case (like 999) do we allocate one new slot for the prepended 1.

When this pattern shows up

Practice