Plus One

NeetCode: Plus One · LeetCode: 66. Plus One · Difficulty: Easy

A non-negative integer is stored as an int[] of digits, most significant first, with no leading zeros (except the number 0 itself). Add one and return the resulting digit array. The number can be too long for any integer type, so the solution works on digits.

Example

Text

Input:  [1, 2, 3]    Output: [1, 2, 4]
Input:  [1, 9, 9]    Output: [2, 0, 0]
Input:  [9, 9]       Output: [1, 0, 0]

Brute force: full school addition into a new array

Add 1 as on paper: start at the last digit with a carry of 1, write (digit + carry) % 10, carry (digit + carry) / 10, and continue left through every digit. The result goes into a new array one slot longer than the input. If a carry is left after the leftmost digit, it fills the extra slot at the front; otherwise that slot is cut off with Arrays.copyOfRange.

Java

import java.util.Arrays;

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        int[] out = new int[n + 1]; // out[0] is the slot for a final carry
        int carry = 1;
        for (int i = n - 1; i >= 0; i--) {
            int sum = digits[i] + carry;
            out[i + 1] = sum % 10;
            carry = sum / 10;
        }
        if (carry > 0) {
            out[0] = carry;
            return out;
        }
        return Arrays.copyOfRange(out, 1, n + 1);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.plusOne(new int[] {1, 2, 3})));
        System.out.println(Arrays.toString(s.plusOne(new int[] {1, 9, 9})));
        System.out.println(Arrays.toString(s.plusOne(new int[] {9, 9})));
        System.out.println(Arrays.toString(s.plusOne(new int[] {0})));
    }
}

Output

[1, 2, 4]
[2, 0, 0]
[1, 0, 0]
[1]

Time: O(n). Space: O(n) for the new array.

Optimal: stop as soon as the carry dies

Both versions are linear. The second uses the fact that a carry only continues through trailing 9s. Walk from the right: a 9 becomes 0 and the carry moves on; any other digit is incremented and the method returns immediately, leaving the rest untouched and using no extra space. Only if every digit was a 9 (like 99) does the loop finish. The answer is then 1 followed by all zeros. A Java array cannot grow, so that case allocates a new array of length n + 1; its elements start at 0, so only the first one is set.

Java

import java.util.Arrays;

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] out = new int[digits.length + 1];
        out[0] = 1;
        return out;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.plusOne(new int[] {1, 2, 3})));
        System.out.println(Arrays.toString(s.plusOne(new int[] {1, 9, 9})));
        System.out.println(Arrays.toString(s.plusOne(new int[] {9, 9})));
        System.out.println(Arrays.toString(s.plusOne(new int[] {0})));
    }
}

Output

[1, 2, 4]
[2, 0, 0]
[1, 0, 0]
[1]

Time: O(n) worst case (all nines); it stops after O(1) steps unless the number ends in a run of nines. Space: O(1) extra, except that the all-nines case allocates an array of length n + 1. This version modifies the input array.