Plus One

How it works

We are given a number represented as an array of digits and need to add one to it.

The simplest way to do this is to simulate how addition works from right to left:

• start from the least significant digit
• if the digit is less than 9, we can increment it and stop
• if the digit is 9, it becomes 0 and we carry +1 to the next digit on the left

If we finish processing all digits and still have a carry, it means the number was something like [9, 9, 9], and we need to add a new leading 1.

Steps

1. Let n be the number of digits.
2. Traverse the digits from right to left:
3. For each index i:
   • If digits[i] < 9:
     • increment digits[i] by 1
     • return the updated list immediately (no further carry)
   • Otherwise (digits[i] == 9):
     • set digits[i] = 0 and continue to the next digit on the left
4. If the loop ends, it means all digits were 9:
   • return [1] + digits
5. The returned list is the result of adding one.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Forgetting to Handle All-Nines Input

When the input is [9, 9, 9], every digit carries over and you need a new leading digit. Returning [0, 0, 0] instead of [1, 0, 0, 0] is a common mistake when the carry-out case is not explicitly handled.

Modifying the Array While Iterating Forward

Starting from index 0 and adding one there ignores how arithmetic carry propagates from the least significant digit. Always process from the last element toward the first to correctly simulate manual addition.

from typing import List

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0

        return [1] + digits

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        vector<int> result(n + 1);
        result[0] = 1;
        return result;
    }
};