Add Strings

• LeetCode: Add Strings

• Problem:

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

• Note:

1. The length of both num1 and num2 is < 5100.

2. Both num1 and num2 contains only digits 0-9.

3. Both num1 and num2 does not contain any leading zero.

4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

• Analysis:

Set carry bit and sum bit. 

Iterate two string to get the added string.

• Code - Java:

public class Solution {
    public String addStrings(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        if (len1 > len2) {
            String temp = num1;
            num1 = num2;
            num2 = temp;
        }
        len1 = num1.length();
        len2 = num2.length();
        StringBuilder builder = new StringBuilder();
        int carry = 0;
        int j = len2 - 1;
        for (int i = len1 - 1; i >= 0; i--) {
            int a = num1.charAt(i) - '0';
            int b = num2.charAt(j) - '0';
            int sum = a + b + carry;
            carry = sum / 10;
            sum %= 10;
            builder.append(String.valueOf(sum));
            j--;
        }
        while (j >= 0) {
            int sum = carry + (num2.charAt(j) - '0');
            carry = sum / 10;
            sum %= 10;
            builder.append(String.valueOf(sum));
            j--;
        }
        if (carry == 1) {
            builder.append("1");
        }
        return builder.reverse().toString();
    }
}

• Code - C++:

class Solution {
public:
    string addStrings(string num1, string num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        if (len1 > len2) {
            string temp = num1;
            num1 = num2;
            num2 = temp;
        }
        len1 = num1.length();
        len2 = num2.length();
        string builder = "";
        int carry = 0;
        int j = len2 - 1;
        for (int i = len1 - 1; i >= 0; i--) {
            int a = num1[i] - '0';
            int b = num2[j] - '0';
            int sum = a + b + carry;
            carry = sum / 10;
            sum %= 10;
            builder += to_string(sum);
            j--;
        }
        while (j >= 0) {
            int sum = carry + (num2[j] - '0');
            carry = sum / 10;
            sum %= 10;
            builder += to_string(sum);
            j--;
        }
        if (carry == 1) {
            builder += "1";
        }
        reverse(builder.begin(), builder.end());
        return builder;
    }
};

• Code - Python:

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        len1, len2 = len(num1), len(num2)
        if len1 > len2:
            num1, num2 = num2, num1
            len1, len2 = len2, len1
        builder = ""
        carry, j = 0, len2 - 1
        for i in range(len1 - 1, -1, -1):
            a, b = ord(num1[i]) - ord('0'), ord(num2[j]) - ord('0')
            sumVal = a + b + carry
            carry = sumVal / 10
            sumVal %= 10
            builder += str(sumVal)
            j -= 1
        while j >= 0:
            sumVal = carry + ord(num2[j]) - ord('0')
            carry = sumVal / 10
            sumVal %= 10
            builder += str(sumVal)
            j -= 1
        if carry == 1:
            builder += str(1)
        return builder[::-1]

• Time Complexity: O(M), M is max(len1, len2)

• Space Complexity: O(M), M is max(len1, len2)