415 Add Strings

1. Description

Given two non-negative integers, nums1 and num2 represented as string, return the sum of num1 and num2 as a string.

 

You must solve the problem without using any buil-in library for handling large integers (such as BigInteger). You must also not convert the input to integers directly.

 

constraints :

• 1 <= num1.length, num2.length <= 104
• num1 and num2 consist of only digits.
• num1 and num2 don't have any leading zeros except for the zero itself.

2. Algorithms

iteration	i	j	num1[i] ("456")	num2[j] ("77")	carry	left
1	2	1	6	7	1	3
2	1	0	5	7	1	3
3	0	-1	4	0	0	5

 

1. Start
2. Declare four variables (i, j, res, carry). 
3. Initialize i, j to length(corresponding list) - 1, and carry to 0, res to empty string.
4. Repeat steps until i or j is smaller than zero.
   1. Initialize two variable val1 and val2 to 0, which store the value of index i and j.
   2. If i or j is bigger than 0, substract 48 from ascii number of value.
   3. Calculate quotient and modulus from division of sum(val1 + val2) and 10, store result into carry and left.
   4. Update result res with summation of left and previous res.
5. Return res out of loop.
6. End

3. Codes

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        # i : variable i will store index of num1 backward
        # j : variable j will store index of num2 backward
        # carry : variable carry will store overflow of num1[i] sum num2[j]
        # res : variable res will store result of leftover
        
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        res = "" 
        
        while i >= 0 or j >= 0 or carry: 
            # This will initialize value of val1 and val2 when if i and j are smaller than 0.
            val1, val2 = 0, 0
            
            if i >= 0 : 
                val1 = ord(num1[i]) - 48 
            if j >= 0 : 
                val2 = ord(num2[j]) - 48 
            
            left = (val1 + val2 + carry) % 10 
            carry = (val1 + val2 + carry) // 10 
            
            i, j = i - 1, j - 1 
            res = str(left) + res 
            
        return res

 

4. Conclusion