Plus One

Description

You are given a large integer represented as an integer array digits, where each digits[i] is the i-th digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading zeros.

Your task is to increment this large integer by one and return the resulting array of digits.

For example, the array [1, 2, 3] represents the integer 123. Adding one gives 124, so you return [1, 2, 4].

Examples

Example 1

Input: digits = [1, 2, 3]

Output: [1, 2, 4]

Explanation: The array represents the integer 123. Adding one gives 123 + 1 = 124. No digit overflows past 9, so the last digit simply changes from 3 to 4.

Example 2

Input: digits = [4, 3, 2, 1]

Output: [4, 3, 2, 2]

Explanation: The array represents 4321. Adding one gives 4322. Again, only the last digit changes.

Example 3

Input: digits = [9]

Output: [1, 0]

Explanation: The array represents 9. Adding one gives 10, which has two digits. The last digit overflows (9 + 1 = 10), producing a carry that creates a new leading digit. The result array is one element longer than the input.

Example 4

Input: digits = [9, 9, 9]

Output: [1, 0, 0, 0]

Explanation: 999 + 1 = 1000. Every digit overflows and the carry propagates all the way through, creating a new leading 1.

Constraints

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

Editorial

Brute Force - Number Conversion

Intuition

The most natural first instinct is to reconstruct the full integer from the digit array, add one to it using normal arithmetic, and then split the result back into individual digits.

Imagine someone hands you a row of sticky notes, each showing a single digit: 1, 2, 3. You would mentally read them as "one hundred twenty-three", add one to get 124, and then write each digit of 124 back onto separate sticky notes.

In Python this is straightforward because Python integers have arbitrary precision — they can hold numbers of any size. In Java you can use the BigInteger class. In C++ there is no built-in big-integer type, so you would need to use a string-based workaround.

Although this approach produces correct results, it performs unnecessary conversions: digits → string → number → string → digits. For a problem that only adds one, these extra steps are wasteful.

Step-by-Step Explanation

Let's trace through with digits = [1, 2, 3]:

Step 1: Join the digits into a string: "123".

Step 2: Convert the string to a number: 123.

Step 3: Add one: 123 + 1 = 124.

Step 4: Convert the result back to a string: "124".

Step 5: Split the string into individual digit characters and convert each back to an integer: [1, 2, 4].

Result: [1, 2, 4].

Now consider digits = [9, 9, 9]:

Step 1: Join: "999".

Step 2: Convert: 999.

Step 3: Add one: 1000.

Step 4: Convert back: "1000".

Step 5: Split: [1, 0, 0, 0].

The approach handles the carry-over case automatically because the arithmetic engine manages the overflow internally.

Algorithm

Build a string by concatenating each digit in the array.
Convert the string to a number (using arbitrary-precision arithmetic).
Add 1 to the number.
Convert the result back to a string.
Map each character of the string to an integer and collect them into the result array.
Return the result array.

Code

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        // Build the number as a string
        string numStr = "";
        for (int d : digits) numStr += to_string(d);

        // Add 1 using character-level arithmetic
        // (C++ has no built-in big integer)
        int carry = 1;
        for (int i = numStr.size() - 1; i >= 0 && carry; i--) {
            int sum = (numStr[i] - '0') + carry;
            numStr[i] = '0' + sum % 10;
            carry = sum / 10;
        }
        if (carry) numStr = "1" + numStr;

        // Convert back to digit array
        vector<int> result;
        for (char c : numStr) result.push_back(c - '0');
        return result;
    }
};

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        # Join digits into a string, convert to int, add 1
        num = int(''.join(str(d) for d in digits))
        num += 1
        # Convert back to list of digits
        return [int(c) for c in str(num)]

import java.math.BigInteger;

class Solution {
    public int[] plusOne(int[] digits) {
        // Build the number as a string
        StringBuilder sb = new StringBuilder();
        for (int d : digits) sb.append(d);

        // Use BigInteger for arbitrary precision
        BigInteger num = new BigInteger(sb.toString());
        num = num.add(BigInteger.ONE);

        // Convert back to digit array
        String s = num.toString();
        int[] result = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            result[i] = s.charAt(i) - '0';
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Building the string from n digits takes O(n). Converting the string to a big integer and adding 1 also takes O(n) internally (big-integer addition is linear in the number of digits). Converting back is another O(n) pass. Total: O(n), but with a higher constant factor due to multiple conversion steps.

Space Complexity: O(n)

We allocate an intermediate string of length n and (in Java) a BigInteger object. The result array itself requires O(n) as well. The auxiliary space for the intermediate representations is O(n).

Why This Approach Is Not Efficient

Although both the brute force and the optimal approach are O(n) in time, the brute force is wasteful in several ways:

Unnecessary conversions. We convert digits → string → number → string → digits. Each conversion allocates new memory and copies data. For a task as simple as "add one", this roundabout path is overkill.
Language-dependent limitations. In C++ there is no built-in arbitrary-precision integer type, so you either overflow with long long (which can only hold ~18 digits) or resort to string arithmetic — which is essentially the same work the optimal approach does, but with the overhead of an intermediate string.
No early termination. The brute force always processes all n digits even when only the last digit changes (e.g., [1, 2, 3] → [1, 2, 4]). If we work directly on the digit array, we can stop as soon as a digit does not overflow.

Key insight: We do not need to reconstruct the full number. We only need to propagate a carry from right to left — and we can do that directly on the input array.

Optimal Approach - Right-to-Left Carry Propagation

Intuition

Think about how you add one by hand on paper. You start from the rightmost digit:

If that digit is less than 9, you simply increase it by one and you are done. No other digit changes.
If that digit is 9, it becomes 0 and you "carry" 1 to the next digit to the left.
You keep carrying leftward until you either reach a digit less than 9 (which absorbs the carry) or you run out of digits.
If you run out of digits and still have a carry, you prepend a 1 (e.g., 999 → 1000).

This is exactly the grade-school addition algorithm, specialized for "plus one". It works directly on the digit array with no conversion, uses no extra space (beyond the potential new digit), and can terminate early the moment the carry is absorbed.

Step-by-Step Explanation

Let's trace through with digits = [2, 9, 9]:

Step 1: Start from the rightmost digit (index 2). Current digit = 9. Add 1: 9 + 1 = 10. Since 10 ≥ 10, set this digit to 0 and carry = 1.

Array: [2, 9, 0]

Step 2: Move left to index 1. Current digit = 9. Add carry: 9 + 1 = 10. Again 10 ≥ 10, so set digit to 0, carry = 1.

Array: [2, 0, 0]

Step 3: Move left to index 0. Current digit = 2. Add carry: 2 + 1 = 3. Since 3 < 10, no overflow. Set digit to 3, carry = 0.

Array: [3, 0, 0]

Step 4: Carry is 0, so we stop. No need to check further.

Result: [3, 0, 0] — which is 299 + 1 = 300. ✓

Now consider the edge case digits = [9, 9, 9]:

Step 1: Index 2: 9 + 1 = 10 → digit = 0, carry = 1. Array: [9, 9, 0]

Step 2: Index 1: 9 + 1 = 10 → digit = 0, carry = 1. Array: [9, 0, 0]

Step 3: Index 0: 9 + 1 = 10 → digit = 0, carry = 1. Array: [0, 0, 0]

Step 4: We have gone past the leftmost digit and carry is still 1. Prepend 1 to the array.

Result: [1, 0, 0, 0] — which is 999 + 1 = 1000. ✓

Plus One — Right-to-Left Carry Propagation — Watch how the carry propagates from the rightmost digit leftward, stopping as soon as a digit absorbs it without overflowing.

Algorithm

Start from the last element of the array (index n − 1).
Add 1 to that digit.
If the result is less than 10, update the digit and return immediately — no carry to propagate.
If the result is 10, set the digit to 0 and move one position to the left. Repeat from step 2 with the next digit.
If you move past index 0 and still have a carry, insert 1 at the front of the array.
Return the array.

Code

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();

        // Traverse from right to left
        for (int i = n - 1; i >= 0; i--) {
            digits[i] += 1;
            if (digits[i] < 10) {
                // No carry — we are done
                return digits;
            }
            // Overflow: set to 0 and carry propagates
            digits[i] = 0;
        }

        // If we exit the loop, every digit was 9
        // Prepend 1 (e.g., 999 -> 1000)
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        n = len(digits)

        # Traverse from right to left
        for i in range(n - 1, -1, -1):
            digits[i] += 1
            if digits[i] < 10:
                # No carry — done
                return digits
            # Overflow: set to 0, carry propagates
            digits[i] = 0

        # All digits were 9 — prepend 1
        return [1] + digits

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;

        // Traverse from right to left
        for (int i = n - 1; i >= 0; i--) {
            digits[i] += 1;
            if (digits[i] < 10) {
                // No carry — done
                return digits;
            }
            // Overflow: set to 0, carry propagates
            digits[i] = 0;
        }

        // All digits were 9 — create new array with leading 1
        int[] result = new int[n + 1];
        result[0] = 1;
        // remaining positions are already 0 by default
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n) worst case, O(1) best case

In the worst case every digit is 9 (e.g., [9, 9, 9]), so we traverse all n digits before prepending 1. This is O(n).

In the best case the last digit is not 9 (e.g., [1, 2, 3]), so we increment it and return immediately. This is O(1).

On average, the expected number of digits we touch is small. The probability that the last k digits are all 9 is (1/10)^k, so the expected number of iterations converges to a constant (~1.11). In practice, this algorithm is extremely fast.

Space Complexity: O(1) extra space

We modify the input array in place. The only case where we allocate new memory is when every digit is 9, requiring a new array of size n + 1. Since the output itself needs that space, the auxiliary space is O(1).

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Plus One

Description

Examples

Example 1

Example 2

Example 3

Example 4

Constraints

Editorial

Brute Force - Number Conversion

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Right-to-Left Carry Propagation

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis