# 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.

### Recommended Posts

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

January 24, 2022

##### Furthest Building You Can Reach | LeetCode | Solution Explained

January 20, 2022

##### Jump Game IV | LeetCode | Solution Explained

January 15, 2022