Teaching Kids Programming – Add Two Big Integers in Strings

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 convert the inputs to 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 <= 10^4
num1 and num2 consist of only digits.
num1 and num2 don’t have any leading zeros except for the zero itself.

Algorithm to Add Two Number Strings

We start adding digits by digits from right (least significant, one’s) to the left (most significant, tens, hundreds …). We need to carry over until all digits have been added.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        n1, n2 = len(num1) - 1, len(num2) - 1
        ans = deque()
        c = 0
        while n1>=0 or n2>=0 or c>0:
            x = c
            if n1>=0:
                x += int(num1[n1])
                n1 -= 1
            if n2>=0:
                x += int(num2[n2])
                n2 -= 1
            ans.appendleft(str(x%10))
            c = x // 10
        return "".join(ans)

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        n1, n2 = len(num1) - 1, len(num2) - 1
        ans = deque()
        c = 0
        while n1>=0 or n2>=0 or c>0:
            x = c
            if n1>=0:
                x += int(num1[n1])
                n1 -= 1
            if n2>=0:
                x += int(num2[n2])
                n2 -= 1
            ans.appendleft(str(x%10))
            c = x // 10
        return "".join(ans)

The time and space complexity is O(Max(A, B)) where A and B are the length of two strings respectively. We use a double-ended queue to store the result and then use the “”.join to concatenate into a string.

See also: How to Add Two Strings Numerically?

–EOF (The Ultimate Computing & Technology Blog) —