66.Plus_One_(Easy).md

66. Plus One (Easy)

Date and Time: Jul 3, 2024, 20:41 (EST)

Link: https://leetcode.com/problems/plus-one/

Question:

You are given a large integer represented as an integer array digits, where each digits[i] is the $i^\text{th}$ digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1, 2, 3]

Output: [1, 2, 4]

Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1, 2, 4].

Example 2:

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

Output: [4,3,2,2]

Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]

Output: [1, 0]

Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Edge case 1:

Input: digits = [9, 9]

Output: [1, 0, 0]

Edge case 2:

Input: digits = [3, 9, 9]

Output: [4, 0, 0]

KeyPoints:

First reverse digits, so if we need to append 0 in the end of digits we can do that. Then we iterate from the reversed digits from left to right (i.e. the last digit -> the first digit), and we increment each digit by 1 if carry = 1. Finally, we check if we need to append an extra 1 if we loop over the last element but we still have a carry like edge case 1.

For example, digits = 99, 99 (reversed) -> 09 (carry=1) -> 00 (carry=1) -> 001 -> 100.

My Solution:

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits = digits[::-1]
        i,carry = 1, 0
        digits[0] += 1
        if digits[0] == 10:
            digits[0] = 0
            carry = 1
        while i < len(digits) and carry == 1:
            if digits[i] == 9:
                digits[i] = 0
                carry = 1
            else:
                digits[i] += 1
                carry = 0
            i += 1
        if carry:
            digits.append(1)
        return digits[::-1]

Time Complexity: $O(n)$
Space Complexity: $O(1)$