[Problem Solving] Plus one to array

Given a non-empty array of digits representing a non-negative integer, plus 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 contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.

Examples:

• [1, 2, 3] should return [1, 2, 4]
• [9, 9] should return [1, 0, 0]

Solution: When we add 1 to a single digit number, there are two outcomes. It can either remain a single digit number or results in 10. If the result is 10, we have to store 0 in the index i and propagate the carry 1 to the previous index i-1.

Let’s traverse the array from the end and add one to the value at index i.

• If the value becomes 10, store 0 in nums[i] and continue traversing the array
• Otherwise, add one to the value at nums[i] and return the array

Time Complexity: Since we traverse the array once, O(N)

Space Complexity: No additional space is used, so O(1)

def plusOne(self, digits: List[int]) -> List[int]:
        
        for i in range(len(digits)-1, -1, -1):
            
            if digits[i] + 1 == 10:
                digits[i] = 0
            else:
                digits[i] += 1
                return digits
            
        return [1] + digits #handle the case where all digits become 9

Testing: For most problems it’s good to test the following cases.

• Empty array: []
• Single value array: [1]
• Array with two values: [1, 8]
• A random array: [1, 2, 3, 4]

In this problem, there are two important cases to test. When the last digit is 9 and when all the digits are 9.

• [1, 9]
• [9] or [9, 9] or [9, 9, 9]

Want to try solving this problem? https://leetcode.com/problems/plus-one/

Hope you enjoyed this simple approach to the plus one problem. Have a great day!