Solution For Add Strings

Problem:

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

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not interpret the inputs as integers directly.

Example 1:
Input: num1 = “11”, num2 = “123”
Output: “134”

Example 2:
Input: num1 = “456”, num2 = “77”
Output: “533”

Example 3:
Input: num1 = “0”, num2 = “0”
Output: “0”

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.

Solution:

The problem can be solved in a straightforward way using the basic addition algorithm that we use to add two numbers manually. We start from the units digit of both the numbers, add them together and take the carry if any to the next digit. We repeat this process until we reach the most significant digit of both the numbers. If any of the numbers still have digits left, we add them to the result.

Let’s implement this algorithm in the code:

class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j, carry, res = len(num1) – 1, len(num2) – 1, 0, ”
while i >= 0 or j >= 0:
x1 = int(num1[i]) if i >= 0 else 0
x2 = int(num2[j]) if j >= 0 else 0
s = x1 + x2 + carry
carry = s // 10
res = str(s % 10) + res
i, j = i – 1, j – 1
return ‘1’ + res if carry else res

In the above code, we first initialize the pointers i and j to the end of both the strings. We also initialize the carry to 0 and the result string to an empty string.

We then enter the loop which runs until we have processed all the digits in both the strings. At each iteration, we extract the digits from the respective positions of the strings (or 0 if we have reached the beginning of a string). We add the two digits together and add the carry from the previous iteration. We then update the carry and add the remainder of the sum to the result string.

Finally, if there is a carry left over, we add a ‘1’ in front of the result string.

That’s it. We have successfully solved the problem using basic addition algorithm.

Time Complexity: O(n), where n is the length of the longer string.

Space Complexity: O(n), for storing the result string.

Step by Step Implementation For Add Strings

/**
 * @author: Jiawei Mao
 * @create: 2019-08-27 12:23
 **/

public class AddStrings {
    public static String addStrings(String num1, String num2) {
        // Set up the string builders for the final answer and for each number
        StringBuilder answer = new StringBuilder();
        StringBuilder sb1 = new StringBuilder(num1);
        StringBuilder sb2 = new StringBuilder(num2);

        // Find the longer number and reverse both numbers
        int len = sb1.length() > sb2.length() ? sb1.length() : sb2.length();
        sb1.reverse();
        sb2.reverse();

        // Perform addition digit by digit
        int carry = 0;
        for (int i = 0; i < len; i++) {
            // Get the digits at position i or 0 if the number is shorter
            int d1 = i < sb1.length() ? sb1.charAt(i) - '0' : 0;
            int d2 = i < sb2.length() ? sb2.charAt(i) - '0' : 0;

            // Perform addition and store the carry
            int sum = d1 + d2 + carry;
            answer.append(sum % 10);
            carry = sum / 10;
        }

        // Add the final carry if it exists
        if (carry != 0) {
            answer.append(carry);
        }

        // Reverse the answer and return
        return answer.reverse().toString();
    }
}

def addStrings(num1, num2): 

# initialize carry to 0 
carry = 0

# initialize an empty string to store the result 
result = "" 

# reverse both num1 and num2 
num1 = num1[::-1] 
num2 = num2[::-1] 

# loop through both strings 
for i in range(max(len(num1), len(num2))): 

	# if i is not within the range of either string, 
	# simply set digit to 0 
	if i >= len(num1): 
		digit = 0
	elif i >= len(num2): 
		digit = 0

	# otherwise, convert the ith digit of 
	# both strings to integers 
	else: 
		digit1 = ord(num1[i]) - ord('0') 
		digit2 = ord(num2[i]) - ord('0') 

	# compute sum of current digits and carry 
	digitSum = digit1 + digit2 + carry 

	# update carry for next iteration 
	carry = digitSum // 10

	# update result 
	result += str(digitSum % 10) 

# if carry is not equal to 0, 
# add it to the result 
if carry != 0: 
	result += str(carry) 

# reverse the string and return 
return result[::-1]

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    // create a variable to store the result
    let result = '';
    // create a variable to keep track of the carry
    let carry = 0;
    // create a variable to keep track of the position in each string
    let i = 0;
    // loop through each string starting from the end
    while (i < num1.length || i < num2.length) {
        // get the digit at the current position in each string
        let digit1 = num1[num1.length - 1 - i] ? num1[num1.length - 1 - i] : '0';
        let digit2 = num2[num2.length - 1 - i] ? num2[num2.length - 1 - i] : '0';
        // convert the digits to numbers
        let num1 = parseInt(digit1);
        let num2 = parseInt(digit2);
        // add the digits and the carry
        let sum = num1 + num2 + carry;
        // if the sum is greater than 9, set the carry to 1
        if (sum > 9) {
            carry = 1;
            sum = sum - 10;
        } else {
            carry = 0;
        }
        // add the sum to the result
        result = sum + result;
        // increment the position
        i++;
    }
    // if there is a carry left over, add it to the result
    if (carry === 1) {
        result = 1 + result;
    }
    // return the result
    return result;
};

class Solution {
public:
    string addStrings(string num1, string num2) {
        // Initialize result
        string result = "";
 
        // Calculate length of both string
        int n1 = num1.length(), n2 = num2.length();
 
        // Reverse both of strings
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
 
        int carry = 0;
        for (int i=0; i= 10)
                carry = 1;
            else
                carry = 0;
 
            // Append sum % 10 to result
            result.push_back(sum % 10 + '0');
        }
 
        // Add remaining carry
        if (carry)
            result.push_back(carry + '0');
 
        // reverse resultant string
        reverse(result.begin(), result.end());
 
        return result;
    }
};

public class Solution {
    public string AddStrings(string num1, string num2) {
        // Initialize result
        string result = "";
 
        // Initialize digit sum
        int sum = 0;
 
        // Traverse both strings starting from the end
        int i = num1.Length - 1, j = num2.Length - 1;
        while (i >= 0 || j >= 0 || sum != 0)
        {
            // Compute sum of last digits and carry
            if (i >= 0)
                sum += num1[i--] - '0';
            if (j >= 0)
                sum += num2[j--] - '0';
 
            // If current digit sum is 1 or 3, add 1 to result
            result = (sum % 10) + result;
 
            // Compute carry
            sum /= 10;
        }
        return result;
    }
}