Problem statement

https://leetcode.com/problems/add-strings/

Solution

What we need to do in this problem is to perform usual schoolbook addition. We need to start to add numbers from the last elements and take care of carry and cases when one number has more digits that another. Imagine that we want to add two numbers: 986 and 47. Then we have the followint steps:

  1. Add 6 and 7, so we have digit 3 and carry equal to 1.
  2. Add 8 and 4 and 1, so we have 3 and carry equal to 1.
  3. Add 9 from first number, and we do not have anything from second, so we choose 0 from second. Also we have curry equal to 1, finally we have digit 0 and carry equal to 1.
  4. We still have carry, but no digits left, so we evaluate 0 + 0 + 1 = 1. And now we can stop, we do not have digits and we do not have carry.

Final number we constructed is 1033.

Complexity

Time complexity is O(m + n), where m and n are lengths of our linked lists, space complexity is O(max(m, n)) if we count answer as memory or O(1) if we do not.

Code

class Solution:
    def addStrings(self, num1, num2):
        l1, l2, carry, ans = len(num1) - 1, len(num2) - 1, 0, []
        while l1 >= 0 or l2 >= 0 or carry:
            d1 = int(num1[l1]) if l1 >= 0 else 0
            d2 = int(num2[l2]) if l2 >= 0 else 0
            carry, digit = divmod(d1 + d2 + carry, 10)
            ans += [str(digit)]
            l1, l2 = l1 - 1, l2 - 1
        
        return "".join(ans[::-1])