66 Plus One

1. Description

You are given a large integer represented as an ineger array digits, where each digits[i] is the ith 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 returning array of digits.

 

constraints :

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0's.

2. Algorithms

This problem same as what we solve at 02 Two Numbers. There are two ways to solve this problem. One is accessing this problem as string, the other is accessing this problem as integer. We will solve this problem with second one. To solve this problem at once, we will iterate over backwards in digits.

1. Initialize overflow as 1 and index as the length of digits. The reason why overflow starts with 1 is our problem is starting plus one with last value.
2. Iterate in while loop, when index of digits become smaller than zero.
   1. Calculation summation of digist[i] and overflow.
   2. Update oveflow as sums mod 10.
   3. Update digits[i] as sums leftover 10.
   4. Increment overflow by -1.
3. There is specific case, when there is 9 in first element. In that case, overflow becomes 1 after escaping the while loop. So, we will insert overflow in index 0 using list.insert() method.
4. Return the result.

Time Complexity : O(N)

Space Complexity : O(1) 

3. Codes

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        overflow = 1
        i = len(digits)-1
        while i >= 0 :
            sums = digits[i] + overflow 
            overflow = sums // 10 
            digits[i] = sums % 10 
            i -= 1
        if overflow != 0 : 
            digits.insert(0, overflow) 
        return digits

4. Conclusion