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.

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)

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

• Invariant: after processing position i, the suffix digits[i:] matches the correct result suffix.
• The formula/transform follows from number properties or monotonicity.
• Each iteration preserves the mathematical invariant.
• Thus the computed value matches the definition of the problem.

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.

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.