# Multiply Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/multiply-strings)
Canonical: https://scaleengineer.com/dsa/problems/multiply-strings
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [X](https://scaleengineer.com/companies/x), [Pinterest](https://scaleengineer.com/companies/pinterest), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [Roku](https://scaleengineer.com/companies/roku)
---
## Problem
Given two non-negative integers `num1` and `num2` represented as strings, return the product of `num1` and `num2`, also represented as a string.

**Note:** You must not use any built-in BigInteger library or convert the inputs to integer directly.

**Example 1:**

**Input:** num1 = "2", num2 = "3"
**Output:** "6"

**Example 2:**

**Input:** num1 = "123", num2 = "456"
**Output:** "56088"

**Constraints:**

* `1 <= num1.length, num2.length <= 200`
* `num1` and `num2` consist of digits only.
* Both `num1` and `num2` do not contain any leading zero, except the number `0` itself.

# Approaches
## Brute Force: Simulating Manual Multiplication
This approach directly mimics the way we perform multiplication by hand. We multiply `num1` by each digit of `num2` one by one, from right to left. Each of these intermediate products is calculated and then added to a running total. To account for the place value of the digit from `num2`, we pad the intermediate product with trailing zeros.
**Time:** O(n * (m + n)) · **Space:** O(m + n)
**Pros:** Conceptually simple and easy to understand as it directly follows the manual method taught in schools.
**Cons:** Highly inefficient due to the repeated creation and manipulation of strings inside a loop.; The `addStrings` operation becomes progressively slower as the `totalSum` string grows in length.
### Explanation
The algorithm iterates through `num2` from the last digit to the first. In each iteration, we take one digit from `num2` and multiply it with the entire `num1`. This single-digit multiplication is itself a loop, where we iterate through `num1`, multiply digits, and handle carries. The result is an intermediate product string. We then append a number of zeros to this intermediate product string corresponding to its place value (e.g., for the tens digit, we add one zero; for the hundreds digit, two zeros, and so on). We then implement a separate function to add this padded intermediate product string to our cumulative result string. This process repeats for all digits in `num2`. The final cumulative result string is the answer.

```java
class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }

        String totalSum = "0";
        int n = num2.length();

        for (int i = n - 1; i >= 0; i--) {
            int digit2 = num2.charAt(i) - '0';
            StringBuilder currentProduct = multiplyByDigit(num1, digit2);
            
            // Append zeros for place value
            for (int j = 0; j < n - 1 - i; j++) {
                currentProduct.append('0');
            }
            
            totalSum = addStrings(totalSum, currentProduct.toString());
        }
        return totalSum;
    }

    // Helper to multiply a string number by a single digit
    private StringBuilder multiplyByDigit(String num, int digit) {
        if (digit == 0) return new StringBuilder("0");
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for (int i = num.length() - 1; i >= 0; i--) {
            int d1 = num.charAt(i) - '0';
            int product = d1 * digit + carry;
            sb.append(product % 10);
            carry = product / 10;
        }
        if (carry > 0) {
            sb.append(carry);
        }
        return sb.reverse();
    }

    // Helper to add two string numbers
    private String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {
            int d1 = (i >= 0) ? num1.charAt(i--) - '0' : 0;
            int d2 = (j >= 0) ? num2.charAt(j--) - '0' : 0;
            int sum = d1 + d2 + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }
}
```
### Algorithm
1. Handle the base case where either `num1` or `num2` is "0". In this case, the product is "0".
2. Initialize a result string, `totalSum`, to "0".
3. Iterate through the digits of `num2` from right to left (from index `n-1` down to `0`).
4. For each digit `d2` in `num2`:
    a. Create a helper function `multiplyByDigit` that takes `num1` and `d2` and returns their product as a string. This function simulates multiplication by iterating through `num1`, multiplying by `d2`, and handling carries.
    b. The result from `multiplyByDigit` is an intermediate product. Append trailing zeros to this intermediate product based on the position of `d2` in `num2`. For a digit at index `i`, append `n-1-i` zeros.
    c. Create another helper function `addStrings` that adds two numbers represented as strings.
    d. Use `addStrings` to add the padded intermediate product to `totalSum`.
5. After the loop finishes, `totalSum` will hold the final product.

## Optimized Grade-School Multiplication
This approach improves upon the manual simulation by avoiding the creation of intermediate strings and performing additions. Instead, it uses an integer array to store the final result and calculates the contribution of each digit pair's product directly into this array. This is based on the observation that the product of the i-th digit of `num1` and the j-th digit of `num2` contributes to the (i+j)-th position of the final result.
**Time:** O(m * n) · **Space:** O(m + n)
**Pros:** Significantly more efficient than the brute-force approach as it avoids costly intermediate string operations.; This is the standard and optimal solution for typical constraints in coding interviews.; The space and time complexity are optimal for this method of multiplication.
**Cons:** The logic for placing products into the correct positions in the result array (`i+j` and `i+j+1`) can be slightly tricky to reason about and implement correctly.
### Explanation
We create an integer array, let's call it `res`, of size `m+n` to store the digits of the final product. We iterate through `num1` and `num2` from right to left using nested loops. Let the current indices be `i` for `num1` and `j` for `num2`. The product of `num1[i]` and `num2[j]` will affect the positions `i+j` and `i+j+1` in our `res` array. `res[i+j+1]` stores the "units" part of the product, and `res[i+j]` stores the "tens" or carry part. For each pair of digits, we calculate their product `mul`. We add this `mul` to the value already at `res[i+j+1]`. The new value at `res[i+j+1]` becomes `(existing_value + mul) % 10`. The carry, `(existing_value + mul) / 10`, is added to `res[i+j]`. After iterating through all digit pairs, the `res` array will contain the final product's digits, possibly with leading zeros. Finally, we convert the `res` array into a string, skipping any leading zeros.

```java
class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        
        int m = num1.length();
        int n = num2.length();
        int[] res = new int[m + n];
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int d1 = num1.charAt(i) - '0';
                int d2 = num2.charAt(j) - '0';
                int mul = d1 * d2;
                
                int p1 = i + j; // Position for carry
                int p2 = i + j + 1; // Position for digit
                
                int sum = mul + res[p2];
                res[p1] += sum / 10;
                res[p2] = sum % 10;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int digit : res) {
            if (!(sb.length() == 0 && digit == 0)) {
                sb.append(digit);
            }
        }
        
        return sb.length() == 0 ? "0" : sb.toString();
    }
}
```
### Algorithm
1. Handle the edge case: if `num1` or `num2` is "0", return "0".
2. The product of two numbers with lengths `m` and `n` can have at most `m+n` digits. Create an integer array `res` of size `m + n` to store the digits of the final product, initialized to zeros.
3. Iterate `i` from `m-1` down to `0` (for `num1`).
4. Inside this loop, iterate `j` from `n-1` down to `0` (for `num2`).
5. For each pair of digits `d1 = num1.charAt(i)` and `d2 = num2.charAt(j)`:
    a. Calculate their product: `mul = d1 * d2`.
    b. The result of this multiplication contributes to two positions in the `res` array. The position for the 'units' digit is `p2 = i + j + 1`, and the position for the 'tens' (carry) is `p1 = i + j`.
    c. Add the product to the existing value at `res[p2]`: `sum = mul + res[p2]`.
    d. The new value at `res[p2]` is the units digit of this sum: `res[p2] = sum % 10`.
    e. The carry is added to the next position: `res[p1] += sum / 10`.
6. After the loops complete, the `res` array contains the product's digits.
7. Convert the `res` array to a string. Iterate through the array, build a `StringBuilder`, and be sure to skip any leading zeros. If the result is all zeros, return "0".

# Solutions
### CSharp

```csharp
public class Solution {
    public string Multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        int m = num1.Length;
        int n = num2.Length;
        int[] arr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int a = num1[i] - '0';
            for (int j = n - 1; j >= 0; j--) {
                int b = num2[j] - '0';
                arr[i + j + 1] += a * b;
            }
        }
        for (int i = arr.Length - 1; i > 0; i--) {
            arr[i - 1] += arr[i] / 10;
            arr[i] %= 10;
        }
        int index = 0;
        while (index < arr.Length && arr[index] == 0) {
            index++;
        }
        StringBuilder ans = new StringBuilder();
        for (; index < arr.Length; index++) {
            ans.Append(arr[index]);
        }
        return ans.ToString();
    }
}
```

### Java

```java
class Solution { public String multiply ( String num1 , String num2 ) { if ( "0" . equals ( num1 ) || "0" . equals ( num2 )) { return "0" ; } int m = num1 . length (), n = num2 . length (); int [] arr = new int [ m + n ]; for ( int i = m - 1 ; i >= 0 ; -- i ) { int a = num1 . charAt ( i ) - '0' ; for ( int j = n - 1 ; j >= 0 ; -- j ) { int b = num2 . charAt ( j ) - '0' ; arr [ i + j + 1 ] += a * b ; } } for ( int i = arr . length - 1 ; i > 0 ; -- i ) { arr [ i - 1 ] += arr [ i ] / 10 ; arr [ i ] %= 10 ; } int i = arr [ 0 ] == 0 ? 1 : 0 ; StringBuilder ans = new StringBuilder (); for (; i < arr . length ; ++ i ) { ans . append ( arr [ i ]); } return ans . toString (); } }
```

### JavaScript

```javascript
/** * @param {string} num1 * @param {string} num2 * @return {string} */ var multiply =
  function (num1, num2) {
    if (num1 === " 0 " || num2 === " 0 ") return " 0 ";
    const result = Array(num1.length + num2.length).fill(0);
    const code_0 = " 0 ".charCodeAt(0);
    const num1_len = num1.length;
    const num2_len = num2.length;
    for (let i = 0; i < num1_len; ++i) {
      const multiplier_1 = num1.charCodeAt(num1_len - i - 1) - code_0;
      for (let j = 0; j < num2_len; ++j) {
        const multiplier_2 = num2.charCodeAt(num2_len - j - 1) - code_0;
        result[i + j] += multiplier_1 * multiplier_2;
      }
    }
    result.reduce((carry, value, index) => {
      const sum = carry + value;
      result[index] = sum % 10;
      return (sum / 10) | 0;
    }, 0);
    return result
      .slice(0, result.findLastIndex((d) => d !== 0) + 1)
      .reverse()
      .join("");
  };

```

### CPP

```cpp
class Solution { public: string multiply ( string num1 , string num2 ) { if ( num1 == "0" || num2 == "0" ) { return "0" ; } int m = num1 . size (), n = num2 . size (); vector < int > arr ( m + n ); for ( int i = m - 1 ; i >= 0 ; -- i ) { int a = num1 [ i ] - '0' ; for ( int j = n - 1 ; j >= 0 ; -- j ) { int b = num2 [ j ] - '0' ; arr [ i + j + 1 ] += a * b ; } } for ( int i = arr . size () - 1 ; i ; -- i ) { arr [ i - 1 ] += arr [ i ] / 10 ; arr [ i ] %= 10 ; } int i = arr [ 0 ] ? 0 : 1 ; string ans ; for (; i < arr . size (); ++ i ) { ans += '0' + arr [ i ]; } return ans ; } };
```

### Python

```python
class Solution:
    def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" m, n = len(num1), len(num2) arr = [0] * (m + n) for i in range(m - 1, - 1, - 1): a = int(num1[i]) for j in range(n - 1, - 1, - 1): b = int(num2[j]) arr[i + j + 1] += a * b for i in range(m + n - 1, 0, - 1): arr[i - 1] += arr[i] // 10 arr[i] %= 10 i = 0 if arr[0] else 1 return "" . join(str(x) for x in arr[i:])

```