Python Grade-School Addition Algorithm [Accepted]


  • 0
    J

    Approach
    The approach uses the same idea as adding numbers when learning addition in grade school. We start from the right-most index on both numbers and add digits as we move to the left of both strings until there are no more digits in either number.

    For example, if we have the numbers "54" and "5", we start at indices 1 and 0, respectively. We add both of 4 and 5 to get 9 with a carry bit of 0. This number is appended to added to the result array at a separately tracked index (in this case, it's 2 because the sum of the lengths of both string versions of 54 and 5 is 3 but 3-1=2). Then, we decrement both indices. On the next iteration, we see that we have reached index -1 for the number 5, so now we only use 5 from index 0 and the carry bit of 0.

    The result array is then joined to get 59.

    Code

    class Solution:
        def addStrings(self, num1, num2):
            num1 = str(num1)
            num2 = str(num2)
            
            l1, l2 = len(num1), len(num2)
            idx1, idx2 = len(num1)-1, len(num2)-1
            result, resultIdx = [""] * (l1+l2), len(l1+l2)-1=
    
            carry = 0
            
            while idx1 >= 0 or idx2 >= 0 or carry:
                v1 = v2 = 0
                
                if idx1 >= 0.:
                    v1 = num1[idx1]
                    idx1 -= 1
                    
                if idx2 >= 0:
                    v2 = num2[idx2]
                    idx2 -= 1                
            
                totalSum = int(v1) + int(v2) + carry
                carry = int(totalSum / 10)
                netSum = totalSum % 10
                
                result[resultIdx] = str(netSum)
                resultIdx -= 1
                
            return "".join(result)
    

    Complexity
    Let N = max(len(str(num1), len(str(num2)). The complexity of this approach is then O(N).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.