Plus One

Given an array of digits representing a non-negative integer, add one and return the resulting digits. Direct integer conversion may overflow for long arrays.

Why this is worth learning

The only digits that propagate an increment are a suffix of nines. Once one non-nine absorbs the carry, every earlier digit is already correct.

Before coding: one-minute experiment

For [1,2,9,9], which digits change? For [9,9], what happens to the original input slice as well as the returned slice?

Function signature

func PlusOne(digits []int) []int

Inputs / outputs

• digits: most-significant digit first.
• Return: digits of the incremented number.

Example

[1,2,3] -> [1,2,4]
[9,9] -> [1,0,0]

Constraints

• 1 <= len(digits) <= 100_000
• 0 <= digits[i] <= 9

Core idea (near-solution)

Treating the whole digit slice as an int would lose support for 100,000-digit inputs. Local addition does not need that conversion: adding one either stops at a non-nine or turns a nine into zero and passes the same carry left. The unprocessed prefix remains untouched as soon as the carry disappears. Only a carry surviving every digit requires a larger result.

Add from the end with a carry. If the carry survives past the first digit, prepend 1.

Invariant: after processing position i, the suffix digits[i:] matches the correct result suffix.

Algorithm (step-by-step)

1. Set carry = 1.
2. Iterate from the last digit to the first:
   • sum = digits[i] + carry.
   • Update digits[i] = sum % 10, carry = sum / 10.
   • If carry == 0, return digits early.
3. If carry > 0, allocate a new slice with leading 1.

Correctness sketch

Working from the least-significant digit, maintain that all processed suffix digits are the correct result and carry is the amount still owed to the next position. Adding carry, storing remainder modulo ten, and updating quotient preserves the invariant. When carry becomes zero, unchanged earlier digits plus the corrected suffix form the full result. If every original digit was nine, all are changed to zero and a new leading one is required. The reference allocates a larger result only in this final case; otherwise it returns the original slice with in-place changes.

Trace (hand walkthrough)

Example input:
[1,2,3] -> [1,2,4]
[9,9] -> [1,0,0]

Walk:
- [1,2,3]: add 1 to last -> [1,2,4]
- [9,9]: 9+1=0 carry1, next 9+carry=0 carry1 -> prepend 1 -> [1,0,0]

Pitfalls to avoid

• Forgetting to handle all-9s.
• Allocating a new slice for every step.

Debugging lens

Test both returned contents and documented mutation. Inputs with leading zeroes retain their width unless a carry grows it; do not normalize them without changing the existing behavior.

Complexity

• Time: O(n).
• Extra space: O(n) only when growing the array.

Implementation notes (Go)

• If carry becomes 0, return early to avoid extra work.

Contract precision

The input slice is mutated. With no growth the result reuses it; on all-nine overflow, a new one-digit-longer slice is returned after the original has been zeroed. Leading zeroes are retained rather than canonicalized.

Reconstruction checkpoint

For [1,2,9,9], which digits change? For [9,9], what happens to the original input slice as well as the returned slice?

Return to Math · Module quiz