Solutions

1. Iteration

O(n) time | O(1) space

Intuition

We can just increase the last element of the array by one.

But when that element is equal to 9, we should update it to 0 and increase the previous element by one instead.

This operation might need to be repeated several times as previous elements might also be equal to 9.

Algorithm

Iterate through the array from the last element to the first with i index.
- If the element at i is less than 9, add 1 to it and return the array.
- Otherwise put 0 into the element at i and continue.
If every element was 9, add 1 to the beginning of the array and return it.

9 + 1 = 10, put 0, carry

1 / 5

Code

def plusOne(digits: list[int]) -> list[int]:
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

/**
 * @param {number[]} digits
 * @returns {number[]}
 */
var plusOne = function (digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++
      return digits
    }
    digits[i] = 0
  }
  return [1, ...digits]
}

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[] carried = new int[digits.length + 1];
        carried[0] = 1;
        return carried;
    }
}