Add Strings - Leetcode Solution

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.

1