Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
num1 and num2 is < 5100.num1 and num2 contains only digits 0-9.num1 and num2 does not contain any leading zero.
Description taken from https://leetcode.com/problems/add-strings/.
#O(Max(M,N)) Time, O(Max(M,N)) Space
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
result = []
carry, pointer_one, pointer_two = 0, len(num1)-1, len(num2)-1
while pointer_one >= 0 or pointer_two >=0:
current_sum = carry
if pointer_one >= 0:
current_sum += ord(num1[pointer_one]) - ord('0')
pointer_one -= 1
if pointer_two >= 0:
current_sum += ord(num2[pointer_two]) - ord('0')
pointer_two -= 1
result.append(str(current_sum % 10))
carry = current_sum // 10
if carry > 0:
result.append(str(carry))
return "".join(result)[::-1]Recall back to grade school when we learned to add two numbers on paper. That is how we can approach this problem.
We will traverse both strings moving right to left, add the numbers and keep track of the carry-over values.
Since we are moving from right to left and appending values to the result from left to right, the result will be reversed once we finish so we will have to reverse it once more.
We will start by initializing our result array, our carry value, and both indices. These index pointers will start at the one's position.
It's also important not to use a string and do some kind of += operation when adding values to it because that would require quadratic time complexity instead of the linear time it takes to append every number to an array.
result = []
carry, pointer_one, pointer_two = 0, len(num1)-1, len(num2)-1
We will then create a loop that will run while one of the pointers still has numbers to sum.
while pointer_one >= 0 or pointer_two >=0:
At the beginning of each iteration, we'll add the carry-over from the previous iteration just like we would on paper.
Initially, this would be zero.
current_sum = carry
During each iteration, we'll sum the current digit in both strings until the index pointer has gone past the zeroth index, meaning we have no more values to add from the given string.
We will add the number using the ASCII lookup table to our current sum before moving our pointer to the next position. This is how we get around converting the string numbers to integers directly.
In this process, we're going from the one's position to the tens, then to the hundreds, etc.
if pointer_one >= 0:
current_sum += ord(num1[pointer_one]) - ord('0')
pointer_one -= 1
if pointer_two >= 0:
current_sum += ord(num2[pointer_two]) - ord('0')
pointer_two -= 1
We will mod our current sum of these two digits by ten and add the non-remainder to our result so we can carry over the remaining value within the next step.
result.append(str(current_sum % 10)
We can get the value that we need to carry into the next iteration by chopping the non-remainder value we just summed in the previous step.
carry = current_sum // 10
If there are any carry values left over once we have broken out of our loop, we will append them to the end of our string.
If we were adding two values on paper, the carry value just becomes the first value of the summed result.
if carry > 0:
result.append(str(carry))
Finally, we will return the reversed result string, since it will be backward from what we want.
return "".join(result)[::-1]