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)
Example for Multiply Strings question
Example for Multiply Strings question
 Example for Multiply Strings question: one layer completed
Example for Multiply Strings question: one layer completed
Example for Multiply Strings question: completed
Example for Multiply Strings question: completed

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.

    Leave a Reply

    Your email address will not be published. Required fields are marked *