Problem Statement in English

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Approach

We simulate the multiplication process as we do it manually. For each digit in the first number, we multiply it with each digit in the second number and store the result in an array.

And we’re done!

Solution in Python


class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        n1, n2 = len(num1), len(num2)
        result = [0] * (n1 + n2)

        for i in reversed(range(n1)):
            for j in reversed(range(n2)):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                tens, ones = i + j, i + j + 1
                total = mul + result[ones]

                result[ones] = total % 10
                result[tens] += total // 10

        prodstring = ""
        for digit in result:
            if not (prodstring == "" and digit == 0):
                prodstring += str(digit)

        return prodstring

Complexity

  • Time: $O(m \times n)$
    Since we are multiplying each digit of num1 with each digit of num2, where m is the length of num1 and n is the length of num2.

  • Space: $O(m + n)$
    Since we are storing the result in an array of size m + n, where m is the length of num1 and n is the length of num2.

Mistakes I Made

I had to look this up :(

And we are done.