Plus One

Array Math

Problem

Given a non-empty array of decimal 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.

For example:

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

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

Thought Process

• How would we approach this problem?

  • This question is about edge cases. We will use a while loop, starting at the end, to loop through the indexes

Solution

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

Key Facts

• If the current element != 9, we can just increment by 1 and return the array.

• If the current element is equal to 9, then we set this element to 0 and go to the preceding element to check.

• If the array isn't returned in the while loop, this means that we had the case of all 9's (like [9,9,9]), so when the while loop breaks, we need to add a 1 to the beginning.

Time Complexity

• Time: $O(n)$because we have to iterate through the array

• Space: $O(1)$