Multiply Strings | LeetCode | Observation Based Approach, Explained

LeetCode 43. Multiply Strings. I explain the Observation Based Approach using simple maths in detail along with the implementation in Python3. Problem Link.

0. Multiply Strings: Problem Discussion

Multiply two numbers given as strings, and return their output as a string.

1. Multiply Strings: Observations & Logic

1.0. Intuitions

• How do we multiply two numbers? Take for example 243 and 19.
• The first thing we do is take the first digit of num2 and multiply all the digits in num1 with it.
• For each of the x*y operations, we also have to take care of the carry-overs. We can do that by temp = carry + x + y.
• The green part is now the remainder on division with 10, and the yellow part is the divisor.
• Finally, when we come to the second digit in num2, we add one more zero at the rightmost position (to account that 1 is actually 10, as in, 19 = 10 + 9)

2. Multiply Strings: Implementation

Once we understand the method, much of remaining solution is implementation.

Here is my naming scheme:

• final_ans stores the total of all the intermediate green rows
• ans is the answer for the intermediate row
• multipler is what takes care of how many zeros have to be added in the rightmost position
• carry keeps a track of the current carry-over (yellow)
• rem is the remainder (green single digits, constituting the green intermediate row)
• position specifies what position in the ans the current rem is – whatever power of 10 we have to raise it

2.0. Code

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        multiplier = 0
        final_ans = 0
        for y in reversed(num2):
            carry = 0
            ans = 0
            position = multiplier
            for x in reversed(num1):
                carry, rem = divmod(carry+int(x)*int(y), 10)
                ans += 10**position * rem
                position += 1
            
            if carry: ans += 10**position * carry
            multiplier += 1
            final_ans += ans
            
        return str(final_ans)

2.1. Complexity Analysis

• Time: O(MN). We iterate over all num1 digits and num2 digits (nested)
• Space: O(1). We only ever store variables: multiplier, position, carry, rem, ans, final_ans.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.