140.Plus One

EasyMath & Geometry · 5/8

Problem

A large non-negative integer is stored as an array digits, most significant digit first, with no leading zeros (except the number 0 itself). Add one to the integer and return the resulting array of digits.

Examples

Input:  digits = [1, 2, 3]
Output: [1, 2, 4]
Explanation: 123 + 1 = 124.

Input:  digits = [4, 3, 2, 9]
Output: [4, 3, 3, 0]
Explanation: 4329 + 1 = 4330 — the 9 rolls over and carries.

Input:  digits = [9, 9, 9]
Output: [1, 0, 0, 0]
Explanation: 999 + 1 = 1000 — the array grows by one digit.

Constraints

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.

💡 Key Insight

Adding one only affects the trailing run of 9s: each 9 becomes 0 and passes a carry left, and the first non-9 digit just increments — then you can stop immediately. Only when every digit is 9 does the array grow, and the answer is then always 1 followed by zeros.

Brute Force (Convert to a Number)

TimeO(n)SpaceO(n)

Intuition

Turn the array into a number, add one, and turn it back into digits. This is how you'd do it by hand, but up to 100 digits overflows long (max ≈ 9.2 × 10^18, 19 digits). It only works with BigInteger, which hides the real lesson and costs extra allocation.

Algorithm

Build a BigInteger from the digits.
Add BigInteger.ONE.
Convert its decimal string back into an int[].

Visualization

[4,3,2,9] -> "4329" -> 4329 + 1 = 4330 -> "4330" -> [4,3,3,0]
with a long, 100 nines would overflow -> must use BigInteger

Code

java

import java.math.BigInteger;

class Solution {
    public int[] plusOne(int[] digits) {
        StringBuilder sb = new StringBuilder();
        for (int d : digits) sb.append(d);
        // long would overflow for more than 18 digits
        String sum = new BigInteger(sb.toString()).add(BigInteger.ONE).toString();
        int[] result = new int[sum.length()];
        for (int i = 0; i < sum.length(); i++) result[i] = sum.charAt(i) - '0';
        return result;
    }
}

Complexity

Time: O(n) — building, adding and converting are linear in the number of digits.
Space: O(n) — the string and big integer.

Carry Simulation

TimeO(n)SpaceO(1) extra, or O(n) when the array grows.

Intuition

Do grade-school addition from the rightmost digit with an initial carry = 1. Each position becomes (digit + carry) % 10 and the new carry is (digit + carry) / 10. If a carry is left after the first digit, prepend a 1.

Algorithm

carry = 1.
For i from n - 1 down to 0: sum = digits[i] + carry, digits[i] = sum % 10, carry = sum / 10.
If carry == 0, return digits; else return [1] followed by digits.

Visualization

digits = [4,3,2,9], carry = 1

i=3: 9+1=10 -> digit 0, carry 1
i=2: 2+1=3  -> digit 3, carry 0
i=1: 3+0=3  -> digit 3, carry 0   (unnecessary work)
i=0: 4+0=4  -> digit 4, carry 0   (unnecessary work)
result [4,3,3,0]

Code

java

class Solution {
    public int[] plusOne(int[] digits) {
        int carry = 1; // the "+1"
        for (int i = digits.length - 1; i >= 0; i--) {
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }
        if (carry == 0) return digits;
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        System.arraycopy(digits, 0, result, 1, digits.length);
        return result;
    }
}

Complexity

Time: O(n) — always visits every digit.
Space: O(1) extra, or O(n) when the array grows.

Early ExitOptimal

TimeO(n) worst case (all 9s); O(1) when the last digit is not 9.

Intuition

As soon as a digit is less than 9, incrementing it absorbs the carry and nothing to its left changes — return right away. If the loop finishes, every digit was 9 and has become 0, so the answer is a fresh array of length n + 1 with a leading 1 (Java zero-initialises the rest).

Algorithm

For i from n - 1 down to 0:
- If digits[i] < 9: increment it and return digits.
- Otherwise set digits[i] = 0 (carry continues).
Return a new array of size n + 1 with result[0] = 1.

Visualization

flowchart TD
    A["i = n-1"] --> B{"digits[i] < 9?"}
    B -->|"yes"| C["digits[i]++<br/>return digits"]
    B -->|"no, it is 9"| D["digits[i] = 0<br/>i--"]
    D --> E{"i >= 0?"}
    E -->|"yes"| B
    E -->|"no: all were 9"| F["return [1, 0, ..., 0]"]

Code

java

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;   // carry absorbed, nothing else changes
                return digits;
            }
            digits[i] = 0;     // 9 + 1 = 10: write 0, carry on
        }
        int[] result = new int[digits.length + 1]; // all digits were 9
        result[0] = 1;
        return result;
    }
}

Complexity

Time: O(n) worst case (all 9s); O(1) when the last digit is not 9.
Space: O(1) extra, O(n) only for the all-9s case.

Complexity Comparison

Approach	Time	Space
BigInteger	O(n)	O(n)
Carry Simulation	O(n)	O(1) / O(n)
Early Exit	O(n) worst, O(1) typical	O(1) / O(n)

Common Pitfalls

Converting to int/long — overflows for long inputs.
Forgetting the all-9s case, which needs one more digit.
Iterating left to right — carries propagate from the least significant (rightmost) digit.
Copying the old digits into the grown array — they are all 0 already, so only result[0] = 1 is needed.