66. Plus One

Problem

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Example 3:

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

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

Discussion

A problem very similar to 2. Add Two Numbers: Mathematical addition for a integer with digits in list. As only 1 is being added to the integer, the algorithm is rather straight forward.

Solution

We perform addition from the last element of list, and carry on addition as long as carry digit exists. For simplicity sake, the starting 1 is also handled as a carry digit.

At last, we have to check and handle if carry digits exists after we loop through all digits in the list.

class Solution:
    def plusOne(self, digits):
        carry = 1
        i = len(digits) - 1

        while carry and i > -1:
            temp = digits[i] + carry
            digits[i] = temp % 10
            carry = temp // 10
            i -= 1

        if carry == 1:
            digits = [1] + digits

        return digits

Complexity Analysis

• Time Complexity: O(n), scanning the whole list at worst.
• Space Complexity: O(1). As only memory and temp sum is in memory.