43. Multiply Strings

MediumMathStringSimulation
Leetcode Link

Problem Description

In this problem, we are given two non-negative integer numbers represented as strings, num1 and num2, and our task is to calculate the product of these two numbers and return the result as a string. The constraint is that we are not allowed to use any built-in library that can handle big integers, nor can we simply convert the strings to integers and multiply them in the standard way. This challenges us to think about how we can perform multiplication manually, mimicking the way one might do it on paper.

Intuition

The intuition behind the solution is based on how we perform multiplication by hand between two numbers. More precisely, when we multiply, say, a three-digit number by a two-digit number, we do it digit by digit and keep track of the carries. This process results in a series of partial products, which are then added together to form the final product.

To implement this in code, we need a data structure to store intermediate results. The approach is to use an array arr to store the digits of the partial products. The length of this array is the sum of the lengths of num1 and num2 because that's the maximum possible length of the result (e.g., 99 * 99 is 9801, four digits long, which is the sum of the lengths of the numbers being multiplied).

Next, we iterate over each digit of num1 and num2 in nested loops, and for each pair of digits, we multiply them and add the result to the corresponding position in arr. The key formula for the index in arr where we should accumulate the product of digits at positions i and j is arr[i+j+1].

After we have all the partial products, we then iterate through the arr array to handle carries at each position, adjusting each digit so that it represents a proper digit in a number (less than 10), and propagating the carry to the next position.

Finally, we need to return the string representation of the number stored in the array, but we skip any leading zeroes, as they don't contribute to the magnitude of the number. We join the remaining digits together to form the resulting product string to be returned.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What data structure does Breadth-first search typically uses to store intermediate states?

Solution Approach

The solution follows these steps:

  1. Check for Zero: If either num1 or num2 is "0", the product is "0". We catch this case early to simplify further logic.

  2. Initialization: Determine the lengths m and n of num1 and num2, respectively. Initialize an array arr of length m + n to hold the digits of the product.

  3. Digit-by-Digit Multiplication:

    • Iterate through the digits of num1 and num2 in descending order using two nested loops, with indices i and j.
    • Convert current digits to integers and multiply them: a * b.
    • Add the multiplication result to an appropriate position in the array arr: arr[i + j + 1] += a * b.
    • The position i + j + 1 comes from the fact that when you multiply a digit at position i of num1 with a digit at position j of num2, the result will contribute to the digits at positions i + j and i + j + 1 of the product.

  4. Handling Carries:

    • Iterate backwards through arr, starting from the end, to process carries.
    • For each position, if the value is greater than 9, divide by 10 to find the carry and keep the remainder:
      • arr[i - 1] += arr[i] // 10: This propagates the carry to the next higher position.
      • arr[i] %= 10: This ensures that the current position has only a single digit.

  5. Converting Array to String:

    • If the digit at the highest position (arr[0]) is zero, it's a leading zero and should be omitted. Determine the starting index for the conversion (i), which is 0 if there's no leading zero, and 1 otherwise.
    • Join the digits from the arr starting at the right index i to form a string without leading zeros: "".join(str(x) for x in arr[i:]).

This implementation doesn't use any special algorithms or data structures—it uses simple arrays and elementary math operations to simulate digit-by-digit multiplication, carefully considering the placement of each partial product and the handling of carries, just like manual multiplication on paper.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example Walkthrough

To illustrate the solution approach, let's walk through a small example where num1 = "13" and num2 = "24".

  1. Check for Zero: Neither num1 nor num2 are "0", so we proceed.

  2. Initialization: The length m of num1 is 2, and the length n of num2 is also 2. We initialize an array arr of length m + n = 4 to [0, 0, 0, 0].

  3. Digit-by-Digit Multiplication:

    • We iterate over num1 and num2 in reverse order so we will have the indices i=1,0 for num1 and j=1,0 for num2.
    • For i=1 (num1[1] = "3") and j=1 (num2[1] = "4"), we multiply the digits and add the result to arr[i + j + 1], which is arr[3] = 0 + (3 * 4) = 12.
    • We store 2 in arr[3] and carry over 1 to arr[2], so arr becomes [0, 0, 1, 2].
    • We repeat this for all pairs of digits:
      • i=1, j=0: arr[2] += 3 (num1[1]) * 2 (num2[0]); arr becomes [0, 0, 7, 2].
      • i=0, j=1: arr[1] += 1 (num1[0]) * 4 (num2[1]); arr becomes [0, 4, 7, 2].
      • i=0, j=0: arr[1] += 1 (num1[0]) * 2 (num2[0]); arr becomes [0, 6, 7, 2].

  4. Handling Carries:

    • Starting from the end of arr, we process the carries:
      • At arr[2] (7): We add 7 // 10 to arr[1] and set arr[2] to 7 % 10. arr stays [0, 6, 7, 2] as 7 is less than 10.
      • At arr[1] (6): We do the same. There's no carry since 6 is also less than 10.

  5. Converting Array to String:

    • arr is [0, 6, 7, 2], so we omit the leading zero.
    • The final product string is "672" as we join the digits from arr starting from index 1.

The final result of multiplying "13" by "24" using our manual algorithm results in "672", which matches what we expect from standard multiplication.

Solution Implementation

1class Solution:
2    def multiply(self, num1: str, num2: str) -> str:
3        # If either number is "0", return "0" because the product will also be "0"
4        if num1 == "0" or num2 == "0":
5            return "0"
6      
7        # Determine the lengths of the input strings
8        length_num1, length_num2 = len(num1), len(num2)
9      
10        # Create a result list to store the product digits
11        result = [0] * (length_num1 + length_num2)
12      
13        # Reverse process of multiplication, processing digits from the end
14        for i in range(length_num1 - 1, -1, -1):
15            digit_num1 = int(num1[i])
16            for j in range(length_num2 - 1, -1, -1):
17                digit_num2 = int(num2[j])
18                # Add product of current digits to the previously stored value in result list
19                result[i + j + 1] += digit_num1 * digit_num2
20      
21        # Handle carrying over digits > 9 to the next place
22        for i in range(length_num1 + length_num2 - 1, 0, -1):
23            result[i - 1] += result[i] // 10  # carry over
24            result[i] %= 10                     # keep only the last digit
25      
26        # Skip leading zeros in the result list
27        start_index = 0 if result[0] != 0 else 1
28      
29        # Convert the result list to string
30        return "".join(str(digit) for digit in result[start_index:])
31
1class Solution {
2    public String multiply(String num1, String num2) {
3        // If either number is 0, the product will be 0.
4        if ("0".equals(num1) || "0".equals(num2)) {
5            return "0";
6        }
7      
8        // Get lengths of both numbers.
9        int length1 = num1.length(), length2 = num2.length();
10      
11        // Initialize an array to store the product of each digit multiplication.
12        int[] productArray = new int[length1 + length2];
13
14        // Loop over each digit in num1 and num2 and multiply them.
15        for (int i = length1 - 1; i >= 0; --i) {
16            int digit1 = num1.charAt(i) - '0';
17            for (int j = length2 - 1; j >= 0; --j) {
18                int digit2 = num2.charAt(j) - '0';
19              
20                // Add the product of the two digits to the corresponding position.
21                productArray[i + j + 1] += digit1 * digit2;
22            }
23        }
24      
25        // Normalize the productArray so that each position is a single digit.
26        for (int i = productArray.length - 1; i > 0; --i) {
27            productArray[i - 1] += productArray[i] / 10; // Carry over the tens to the next left cell.
28            productArray[i] %= 10; // Keep the units in the current cell.
29        }
30      
31        // Skip the leading 0 in the product array if it exists.
32        int startIndex = productArray[0] == 0 ? 1 : 0;
33      
34        // Convert the product array into a string.
35        StringBuilder product = new StringBuilder();
36        for (int i = startIndex; i < productArray.length; ++i) {
37            product.append(productArray[i]);
38        }
39        return product.toString();
40    }
41}
42
1class Solution {
2public:
3    string multiply(string num1, string num2) {
4        // Check if either input is "0", if yes, then result is "0"
5        if (num1 == "0" || num2 == "0") {
6            return "0";
7        }
8
9        // Initialize the sizes of the input numbers
10        int length1 = num1.size(), length2 = num2.size();
11
12        // Create a vector to store the multiplication result
13        vector<int> result(length1 + length2, 0);
14
15        // Multiply each digit of num1 with each digit of num2
16        for (int i = length1 - 1; i >= 0; --i) {
17            int digit1 = num1[i] - '0'; // Convert char to integer
18            for (int j = length2 - 1; j >= 0; --j) {
19                int digit2 = num2[j] - '0'; // Convert char to integer
20                // Add to the corresponding position in the result vector
21                result[i + j + 1] += digit1 * digit2;
22            }
23        }
24
25        // Handle carrying over the value for digits greater than 9
26        for (int i = result.size() - 1; i > 0; --i) {
27            result[i - 1] += result[i] / 10; // Carry over
28            result[i] %= 10; // Remainder stays at current position
29        }
30
31        // Skip any leading zeros in the result vector
32        int startIndex = result[0] == 0 ? 1 : 0;
33
34        // Convert the result vector to a string
35        string resultStr;
36        for (int i = startIndex; i < result.size(); ++i) {
37            resultStr += '0' + result[i]; // Convert integer to char and append to resultStr
38        }
39
40        // Return the final product as a string
41        return resultStr;
42    }
43};
44
1// Multiplies two non-negative integers represented as number strings and returns the product as a string.
2function multiply(num1: string, num2: string): string {
3    // If either number is '0', the product will be '0'.
4    if ([num1, num2].includes('0')) return '0';
5
6    // Get the lengths of the two number strings.
7    const length1 = num1.length;
8    const length2 = num2.length;
9    let answer = '';
10
11    // Iterate over each digit in the first number.
12    for (let i = 0; i < length1; i++) {
13        let currentDigit1 = parseInt(num1.charAt(length1 - i - 1), 10);
14        let partialSum = '';
15
16        // Iterate over each digit in the second number.
17        for (let j = 0; j < length2; j++) {
18            let currentDigit2 = parseInt(num2.charAt(length2 - j - 1), 10);
19
20            // Multiply current digits and add them to the partial sum with proper offset.
21            partialSum = addString(partialSum, (currentDigit1 * currentDigit2) + '0'.repeat(j));
22        }
23
24        // Construct the answer with the accumulated partial sum with proper offset.
25        answer = addString(answer, partialSum + '0'.repeat(i));
26    }
27  
28    // Return the final product as a string.
29    return answer;
30}
31
32// Adds two number strings and returns the sum as a string.
33function addString(numString1: string, numString2: string): string {
34    const length1 = numString1.length;
35    const length2 = numString2.length;
36    let answerArray = [];
37    let carry = 0;
38
39    // Add the two strings together, digit by digit, from the end to the beginning.
40    for (let i = 0; i < Math.max(length1, length2) || carry > 0; i++) {
41        let digit1 = i < length1 ? parseInt(numString1.charAt(length1 - i - 1), 10) : 0;
42        let digit2 = i < length2 ? parseInt(numString2.charAt(length2 - i - 1), 10) : 0;
43      
44        // Calculate the sum for current place and maintain the carry for the next iteration.
45        let sum = digit1 + digit2 + carry;
46        answerArray.unshift(sum % 10);
47        carry = Math.floor(sum / 10);
48    }
49  
50    // Join the computed digits to form the final sum string.
51    return answerArray.join('');
52}
53
Not Sure What to Study? Take the 2-min Quiz：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

Time Complexity: The time complexity of the given code is O(m * n), where m and n are the lengths of the input strings num1 and num2 respectively. The code involves a double loop where the outer loop runs m times and the inner loop runs n times, leading to m * n multiplication operations. Additionally, there is a loop for carrying over the values, which runs in O(m + n) time. However, since O(m * n) dominates O(m + n), the overall time complexity stays O(m * n).

Space Complexity: The space complexity is O(m + n), as an additional array arr of size m + n is used to store the intermediate results of the multiplication before they are converted to the final string result.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫