Solutions

# Iterarive or recursive. Handle the carry when adding 1 to the last digit, and propagate it to the left if needed. If we reach the leftmost digit and still have a carry, we need to add a new digit at the front.
# math


# O(n) time, O(n) space
def plusOne(digits: list[int]) -> list[int]:
    digits[-1] += 1

    newdigits = []
    carry = 0
    for d in reversed(digits):
        digit = (d + carry) % 10
        carry = (d + carry) // 10
        newdigits.append(digit)

    if carry != 0:
        newdigits.append(carry)

    return newdigits.reverse()


# Recursive - O(n) time, O(n) space
def plusOne(digits: list[int]) -> list[int]:
    if not digits:
        return [1]

    if digits[-1] < 9:
        digits[-1] += 1
        return digits
    else:
        return plusOne(digits[:-1]) + [0]