# 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: one layer 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.

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

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.