Skip to main content
CodeEasy v0.1

Multiply Strings

Medium Subject: Math & Geometry
Time Complexity
O(M * N)
Space Complexity
O(M + N)

Problem Description

Problem Statement

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. 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"

Optimal Solution

Python

Approach: Grade School Multiplication Array

Initialize an array res of size len(num1) + len(num2) filled with zeros. Multiply each digit of num1 with each digit of num2. Add the result to res[i + j + 1]. Handle carry-overs by adding to res[i + j]. Finally, convert the array to a string, skipping leading zeros.

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

        m, n = len(num1), len(num2)
        res = [0] * (m + n)

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = int(num1[i]) * int(num2[j])
                p1, p2 = i + j, i + j + 1
                total = mul + res[p2]

                res[p1] += total // 10
                res[p2] = total % 10

        result_str = "".join(map(str, res))
        return result_str.lstrip('0')