Sweaty Imposter

Plus One

EasyMath & GeometryNeetCode 150JuniorOpen on LeetCodeUpdated

You're given a non-empty array digits that represents a non-negative integer, most significant digit first. There are no leading zeros, except in the number 0 itself. Add one to the integer and return the resulting digits in the same form.

Examples

digits = [4,0,7] returns [4,0,8]

407 + 1 = 408. There is no carry, so only the last digit changes.

digits = [2,9,9] returns [3,0,0]

The trailing nines turn into zeros, and the carry stops at the 2.

digits = [9,9,9] returns [1,0,0,0]

Every digit is 9, so the result needs one more digit than the input.

Constraints

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits has no leading zeros, except in the number 0 itself.

Hints

Hint 1

When you add one by hand, which digits can change?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Walk from the last digit toward the front. If the digit is less than 9, increment it and return right away, since nothing carries further. Otherwise it is a 9: set it to 0 and keep moving left with the carry. If the loop passes the first digit, every digit was 9, so return a new array of length n + 1 with a 1 followed by zeros. O(n) time, and O(1) extra space except in the all-nines case.

Time

O(n)

Space

O(1), or O(n) when every digit is 9

Pitfall

Converting the digits to a number, adding one, and converting back. A 100-digit number overflows a long, so the Java version breaks on large inputs. Work on the digits directly.

Solutions

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;
    }
}
Drill This