For today’s challenge, we’ll be working on the Multiply Strings problem from Leetcode.
Table of Contents
The Multiply Strings Problem
This problem requires us to write a function called multiply() that accepts two non-negative integers – num1 and num2 – represented as strings. The function should return the product of num1 and num2, also represented as a string.
For instance,
multiply('2', '3') should return '6' (as 2*3 = 6)
multiply('123', '45') should return '5535' (as 123*45 = 5535)
The challenge for this problem is that you are not allowed to convert the inputs to integers directly. For instance, if the inputs are '123' and '45', you are not allowed to convert them to 123 and 45 directly.
Suggested Approach
To solve the Multiply Strings problem, we’ll be converting individual digits (as opposed to the entire input) in num1 and num2 to integers and multiplying pairs of digits from the two strings.
For instance, if num1 = '123', we’ll convert '1' to 1, '2' to 2 and so on. We’ll then multiply each digit in num1 with another digit in num2 and add the product to our result.
The approach can be broken down into the following steps; we’ll explain these steps in detail later.
Step 1
Declare a list called result with a length of len(num1) + len(num2). Initialize all the elements in result to 0.
Step 2
Iterate through num1 and num2, starting from right to left. Convert each digit to an integer and multiply each digit in num1 (denoted as num1[i]) with each digit in num2 (denoted as num2[j]).
Step 2a
For each i and j, add num1[i] * num2[j] to result[i+j+1]
Step 2b
Account for any carry over if the product in Step 2a is greater than 9
Step 3
After iterating through all the digits in num1 and num2, convert result back to a string
Step 4
Return the resulting string
Example
Let’s use an example to illustrate how this approach works for the Multiply Strings problem.
Suppose num1 = '123' and num2 = '45'.
Step 1: Declare a list called result
We’ll first declare a list called result, with a length of 5 and an initial value of zero for all its elements. In other words, result = [0, 0, 0, 0, 0].
The length of result should be 5 as the product of a 3-digit number with a 2-digit number will have at most 5 digits. This is because the greatest 3-digit number (999) multiplied with the greatest 2-digit number (99) gives us 99,999 (which is 5-digit).
Step 2: Iterate through num1 and num2
Next, we’ll iterate through num1 and num2, starting from right (i.e. the last digit, with an index of -1) to left.
Iteration 1
On the first iteration, we’ll convert num1[-1] and num2[-1] to integers and multiply them together. This gives us 3*5 = 15. We’ll add this value to result[(-1)+(-1)+1] = result[-1].
result becomes [0, 0, 0, 0, 15].
As 15 is greater than 9, we’ll add the carry over to result[-2] and update result[-1].
result becomes [0, 0, 0, 1, 5].
Iteration 2
Next, we multiply the integers of num1[-1] and num2[-2]. This gives us 3*4 = 12. We’ll add this value to result[(-1)+(-2)+1] = result[-2].
result becomes [0, 0, 0, 13, 5].
As 13 is greater than 9, we’ll add the carry over to result[-3] and update result[-2].
result becomes [0, 0, 1, 3, 5].
We keep iterating through the digits in num1 and num2 until we finish all the digits.
Step 3: Convert result back to a string
After iterating through all the digits in num1 and num2, result stores the digits for the product of 123 and 45. In other words,
result = [0, 5, 5, 3, 5].
We’ll convert this list to the string '5535'.
Step 4: Return the resulting string
Finally, we return the string '5535'.
Explanation for Step 2a
Of all the steps above, Step 2a should be the hardest to understand.
To understand how this step works, let’s look at the iterations for num1 = '123' and num2 = '45', as shown in the diagram below:
Example 1
We’ll use iteration 4 to illustrate. Here, we multiply the tens (10) digit in num1 with the tens (10) digit in num2. As 10×10 = 100, the result of the multiplication should be in the hundreds.
Specifically,
num1[-2] = '2'
num2[-2] = '4'
After we convert num1[-2] and num2[-2] to integers and multiply them, we get 2*4 = 8.
'2' in num1 stands for 20 and '4' in num2 stands for 40.
As 20*40 = 800, the product 8 we got by multiplying the integers of num1[-2] and num2[-2] actually stands for 800. Hence, we add 8 to the hundreds digit (i.e. the blue cell) for result.
Example 2
Next, let’s consider another example. We’ll use iteration 6 to illustrate this time.
Here, we multiply the hundreds (100) digit in num1 with the tens (10) digit in num2. As 100×10 = 1000, the result of the multiplication should be added to the thousands digit in result. Hence, we add 5 to the thousands digit (the blue cell) in result.
The same logic applies to all the other iterations.
Getting the index for result
The difficult part in our suggested solution is figuring out the correct index for result to add the product of num1[i] and num2[j] to.
This can be done through observation.
If you study all the iterations above, you’ll probably notice that in general, when we multiply num1[i] with num2[j], the correct index for result is given by the formula i+j+1.
For instance, for iteration 4, i = -2 and j = -2. We add the product of num1[-2] and num2[-2] to index -3 in result.
-3 can be found using (-2) + (-2) + 1.
For iteration 6, we add num1[-3]*num2[-2] to result[-4].
-4 can be found using (-3) + (-2) + 1.
The same applies to all the other iterations. You can try them yourself to verify it.
Based on the explanation and description above, try working on this challenge yourself.
The approach described above for solving the Multiply Strings problem is summarized in the graphical illustration below.
Graphical Illustration
Suggested Solution
def multiply(num1, num2):
integers = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}
iStrings = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
# Step 1: Declare and initialize result
result = [0]*(len(num1) + len(num2))
str_result = ''
# Step 2: Iterate through num1 and num2, from right to left
for i in range(-1, -1*len(num1)-1, -1):
for j in range(-1, -1*len(num2)-1, -1):
# Step 2a: Add product to result
result[i+j+1] += integers[num1[i]]*integers[num2[j]]
# Step 2b: Account for carry over
result[i+j] += result[i+j+1] // 10
result[i+j+1] %= 10
# Step 3: Convert result to string
for j in result:
str_result += iStrings[j]
str_result = str_result.lstrip('0')
# Step 4: Return string
return '0' if (str_result == '') else str_resultIn the suggested solution above, we first declare a dictionary called integers. This dictionary maps a single-digit string to an integer. For instance, integers['0'] gives us the integer 0, integers['1'] gives us 1 and so on. We’ll use this dictionary to convert the digits in our input strings to integers later.
Next, we declare a list called iStrings. This list consists of string elements that correspond to their indexes. For instance, iStrings[0] gives us the string '0', iStrings[1] gives us '1' and so on. We’ll be using this list to convert single-digit integers back to strings.
Step 1
On line 7, we declare and initialize result.
Next, we declare a variable called str_result that’ll be used to store the result of our multiplication as a string.
Step 2
From lines 11 to 19, we iterate through num1 and num2 from right to left using two for loops.
Step 2a
Inside the inner for loop, we use the integers dictionary to convert num1[i] and num2[j] to integers. Next, we multiply the two integers and add the product to result[i+j+1] on line 15.
Step 2b
On lines 18 and 19, we perform two mathematical operations to account for any carry over.
Suppose result = [0, 0, 7, 13, 5], i = -2 and j = -1, we need to do carry over for result[-2].
On line 18,
result[i+j] += result[i+j+1] // 10 becomes result[-3] = result[-3] + (result[-2] // 10) = result[-3] + (13//10) = result[-3] + 1 = 8
result becomes [0, 0, 8, 13, 5].
On line 19,
result[i+j+1] %= 10 becomes result[-2] = result[-2] % 10 = 13 % 10 = 3
As a result, result is updated from [0, 0, 7, 13, 5] to [0, 0, 8, 3, 5]. This shows an example of how carry over is done.
On the other hand, suppose result = [0, 0, 7, 6, 5], we do not need to do any carry over. Lines 18 and 19 will have no effect on result if all the elements in result are smaller than 10.
Suppose, i = -1 and j = -1,
On line 18
result[i+j] += result[i+j+1] // 10 becomes result[-2] = result[-2] + (result[-1] // 10) = result[-2] + (5//10) = result[-2] + 0 = 6
On line 19
result[i+j+1] %= 10 becomes result[-1] = result[-1] % 10 = 5 % 10 = 5
result remains as [0, 0, 7, 6, 5] after lines 18 and 19. That is, no carry over is done.
Step 3
After iterating through all the digits in num1 and num2 and completing steps 2a and 2b, result stores the digits of the product of num1 and num2.
From lines 22 to 25, we convert result back to a string. We do that by using the iStrings list to convert each digit to a string and appending the result to a variable called str_result (on line 23).
Next, we use the built-in Python function lstrip('0') to remove any leading '0' from str_result. For instance, if result = [0, 5, 5, 3, 5],
str_result = '05535'
Line 25 removes the leading '0' and assigns the result '5535' back to str_result.
Step 4
On line 28, we return the value of str_result.
However, before we do that, we first check if str_result is an empty string. If it is, we return '0'. Else, we return str_result.
With that, the function is complete.