Plus One

The machine gets an array of digits forming a big integer, most significant first, and must add one and return the resulting digits. The work happens at the right edge: add one to the last digit; if that produces 10, carry left and continue. The array is the number — there is no integer type wide enough for 100-digit inputs, so converting to int is not an option.

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

Steps: (1) walk from the last digit backward, (2) the first digit below 9 just increments — all digits to its right are 9 (they would have carried otherwise), so the array is already correct, (3) if every digit was 9, every digit becomes 0 and a leading 1 is prepended.

Time is O(n) worst case (all nines), O(1) average. Space is O(1) except the all-nines case, which allocates one new slot.

Trickiest edge case: [9,9,9] → [1,0,0,0]. The result is one digit longer and cannot be done fully in place — prepending requires a new array. The loop must return immediately on the non-carry path, or later iterations corrupt digits that were already final.