Plus One

Difficulty: Easy

You're given a very large, non-negative number, represented as a list of its digits in order (so [1, 2, 3] represents the number 123). The list has no leading zeros, except for the number 0 itself.

Add one to this number, and return the new digits as a list, in the same order.

Examples

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

123 + 1 = 124.

Input: digits = [9, 9, 9]
Output: [1, 0, 0, 0]

999 + 1 = 1000 - the extra digit means the result has one more digit than the input.

Input: digits = [0]
Output: [1]

Constraints

  • 1 <= digits.length <= 100

  • 0 <= digits[i] <= 9

  • digits does not contain any leading zeros, except for the number 0 itself.

Approach

A tempting shortcut is to treat the whole digit list as one big number: join the digits into a string, add one to it, and split the result back into digits. That works, but leans on being able to represent arbitrarily large numbers accurately - something that's only safe here because of a big-number type; it wouldn't hold up with an ordinary floating-point number once the digit list gets long enough to lose precision.

The more robust way mirrors how you'd add one by hand: start from the last digit. If it isn't a 9, just add one to it and you're done - nothing else changes. If it is a 9, it wraps around to 0 and you have to carry the 1 into the digit to its left, repeating the same check there. The only special case is when every digit was a 9 (like 999), which means the carry runs off the front of the number entirely and a new leading 1 has to be added.

Solutions

Convert to a Number

Join the digits into a string, convert it to a big-number type so precision isn't lost, add one, and split the result back into individual digits.

function plusOne(digits) {
  const num = BigInt(digits.join(""));
  const incremented = (num + 1n).toString();
  return incremented.split("").map(Number);
}

Time: O(n) · Space: O(n)

Optimal - Digit by Digit With Carry

Walk the digits from right to left. As soon as a digit is less than 9, adding one to it is enough - return immediately. Otherwise, that digit wraps to 0 and the carry moves one position further left. If the carry makes it all the way past the front, every digit was a 9, so prepend a new leading 1.

function plusOne(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++;
      return digits;
    }
    digits[i] = 0;
  }

  // Every digit was a 9 (e.g. 999 -> 1000): prepend a new leading 1
  return [1, ...digits];
}

Time: O(n) · Space: O(1) extra space, aside from the rare case that adds a new leading digit