Plus One

You are given a large integer as an array digits, where digits[i] is the i-th digit and the most significant digit comes first. The number has no leading zeros, except for the number 0 itself. Add one to the number and return the resulting array of digits.

The limits are 1 <= digits.length <= 100 and 0 <= digits[i] <= 9. A 100-digit number is far too large for a long. This is LeetCode 66.

Example 1
Input: digits = [1, 2, 3]
Output: [1, 2, 4]
Example 2
Input: digits = [4, 3, 2, 1]
Output: [4, 3, 2, 2]
Example 3
Input: digits = [9]
Output: [1, 0]
Explanation: 9 + 1 = 10, which needs one more digit.

How to Think About It

Step 1: Why not convert to a number

Building an int or long from the digits overflows once the value passes Long.MAX_VALUE, about 9.2 × 10^18, and the input can have 100 digits. So the addition has to happen on the array itself, the way you add on paper.

Step 2: Adding one only touches a tail of nines

Start at the last digit. If it is less than 9, add 1 and you are done: no carry is created, so nothing to its left changes. That is the common case, and it costs a single step.

Step 3: A 9 becomes 0 and passes the carry on

If the digit is 9, then 9 + 1 = 10: write 0 and carry 1 to the next digit on the left. Repeat. The carry stops at the first digit from the right that is not 9, so 1299 becomes 1300.

Step 4: The all-nines case

If every digit is 9, the loop turns them all into 0 and the carry falls off the left end. The answer is 1 followed by n zeros, which needs a new array one longer than the input. This is the only input where the length changes.

Walkthrough

The input digits = [1, 9, 9], where the carry travels two places before it stops.

idigits[i]ActionArray after
29write 0, carry 1[1, 9, 0]
19write 0, carry 1[1, 0, 0]
011 < 9, so write 2 and return[2, 0, 0]

For [9, 9, 9] all three digits become 0, the loop ends without returning, and the method returns the new array [1, 0, 0, 0].

Java Solution

The method walks from the last digit to the first, turning nines into zeros until it finds a digit it can raise by one.

  • The carry is implicit: while the loop runs, a carry of 1 is always waiting to be added. Reaching index i means every digit to its right was a 9 that is now a 0.
  • Early return: a digit below 9 absorbs the carry, so the method returns right there. For [1, 2, 3] the loop runs once.
  • All nines: reaching the code after the loop means every digit was 9. A new int array is filled with zeros by Java, so only result[0] = 1 needs to be set.
  • In place: the method changes the input array and returns it in every case except all nines. [0] becomes [1].

A common mistake is to return digits after the loop as well. Every all-nines input then loses its leading 1, so [9, 9, 9] returns [0, 0, 0] and [9] returns [0].

Java
public class PlusOne {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits; // no carry left, the digits to the left stay the same
            }
            digits[i] = 0;     // 9 + 1 = 10: write 0 and carry 1 to the left
        }
        int[] result = new int[digits.length + 1]; // every digit was 9, e.g. 999 + 1 = 1000
        result[0] = 1;
        return result;
    }
}

Complexity

  • Time: O(n), where n is the number of digits. The loop visits each digit at most once from the right, and it stops at the first digit below 9. Only an all-nines input visits every digit and then fills a new array.
  • Space: O(1) extra in every case but one, because the digits are changed in place. The all-nines input needs a fresh array of n + 1 digits, which is also the size of the answer.

The method matched BigInteger on 100,000 random arrays of up to 100 digits, including many runs of nines. Adding two whole numbers digit by digit is Add Strings, and the same carry logic on a linked list is Add Two Numbers.