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 rowsans
is the answer for the intermediate rowmultipler
is what takes care of how many zeros have to be added in the rightmost positioncarry
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 theans
the currentrem
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
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022