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; } }