Multiply Strings

String Math

Problem

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 have any leading zeroes.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

For example:

Input: num1 = "2", num2 = "3"
Output: "6"

Input: num1 = "123", num2 = "456"
Output: "56088"

Thought Process

• We are simulating the multiplication process by taking numbers digit by digit, and keep multiplying the digit with the other number and maintaining the sum in a separate array.

• We can get the index in the result array of where the product of the two digits should be placed by taking the addition of the original index of the two numbers and adding 1 (this positon is also where the last carry digit will be present)

  • If a carry digit is already in this position, we sum it to the product, take the quotient, and place the carry in the next positon

• Different from Add Strings, we have two for loops, instead of a while loop and two pointers, because we need to multiply each digit in one number with all the other digits in the other number.

Solution

Version 1

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        n = len(num1)
        m = len(num2)
        vals = [0 for i in range(n+m)]
        for j in range(m-1,-1,-1):
            for i in range(n-1,-1,-1):
                mult = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                numSum = vals[i+j+1] + mult
                vals[i+j] += numSum//10 #carry
                vals[i+j+1] = numSum % 10 #remainder
        res = ""
        
        for i in range(len(vals)):
            #ensures we don't append 0 to the beginning
            if len(res) != 0 or vals[i] != 0: 
                res+=str(vals[i])
                
        if len(res) == 0:
            return "0"
        else:
            return res

Checking for leading zeroes alternative

        for i in range(len(vals)):
            if len(res) == 0 and vals[i] == 0:
                continue
            else:
                res+=str(vals[i])

Key Facts

• Need two for loops to simulate multiplying each digit in one number with the digits in the other number

• Need a "sum" array that will simulate all the addition operations when a carry is needed to be added to the product of two digits. This sum array will also be our output array

• In our "sum" array, we are storing the quotient of a product in one slot and the remainder (which is the carry variable) in the other slot.

• Need to check for leading zeroes

Time Complexity

• Time: $O(n^2)$

• Space: $O(n+m)$