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
- 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_ansstores the total of all the intermediate green rows
ansis the answer for the intermediate row
multipleris what takes care of how many zeros have to be added in the rightmost position
carrykeeps a track of the current carry-over (yellow)
remis the remainder (green single digits, constituting the green intermediate row)
positionspecifies what position in the
remis – whatever power of 10 we have to raise it
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.
June 13, 2022
January 24, 2022