Teaching Kids Programming – High Accuracy Multiplication Algorithm (Multiply Strings)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:
Input: num1 = “2”, num2 = “3”
Output: “6”

Example 2:
Input: num1 = “123”, num2 = “456”
Output: “56088”

Constraints:
1 <= num1.length, num2.length <= 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.

High Accuracy Multiplication Algorithm (Multiply Strings)

Python’s integer variable can hold arbitrary length of digits so a quick cheat would be to convert to int, do the multiplication and then convert back to string:

1
2
3

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        return str(int(num1)*int(num2))

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        return str(int(num1)*int(num2))

Most programming languages have int type – which is probably 32-bit integer so it can hold unsigned value from 0 to . Give number a (n digits) and number b (m digits), the result could have at most (n+m) digits, thus we can allocate an array/list which is initialized to all zeros to hold the result.

For simplicity, we don’t consider the negative numbers but which should be easy to handle, aka two negatives make positive and one makes negative.

We can reverse both inputs, so that we can loop from the 0 which is the less significant digit. And we store multiplication result of a[i]*b[j] to ans[i+j] but we need to carry over to the next digit.

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

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        n1, n2 = len(num1), len(num2)
        ans = [0] * (n1 + n2)
        num1 = num1[::-1]
        num2 = num2[::-1]
        for i in range(n1):
            for j in range(n2):
                ans[i + j] += (ord(num1[i]) - 48) * (ord(num2[j]) - 48)
                ans[i + j + 1] += ans[i + j] // 10
                ans[i + j] %= 10
        x = "".join(map(str, ans[::-1])).lstrip('0')
        return x if x else "0"

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        n1, n2 = len(num1), len(num2)
        ans = [0] * (n1 + n2)
        num1 = num1[::-1]
        num2 = num2[::-1]
        for i in range(n1):
            for j in range(n2):
                ans[i + j] += (ord(num1[i]) - 48) * (ord(num2[j]) - 48)
                ans[i + j + 1] += ans[i + j] // 10
                ans[i + j] %= 10
        x = "".join(map(str, ans[::-1])).lstrip('0')
        return x if x else "0"

The time complexity is O(NM) and the space complexity is O(N+M). The ans is a type of array of digits, first, we reverse it, then we convert it to array of strings, and then we join/concatenate the array, and finally, we strip out left/leading zeros (string trim left function).

If the result becomes empty – then we need to return “0” instead.

See also: Algorithm to Multiply Two Big Integers (String)

–EOF (The Ultimate Computing & Technology Blog) —