LeetCode Problem

Problem Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Examples

Input: 2, 3
Output: 6

Input: 123, 456
Output: 56088

Constraints

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

Follow-up

Approach to Solve

Use the elementary multiplication algorithm with optimizations.

Code Implementation

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        m, n = len(num1), len(num2)
        result = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                p1, p2 = i + j, i + j + 1
                total = mul + result[p2]
                result[p1] += total // 10
                result[p2] = total % 10
        res = ""
        for digit in result:
            if res or digit != 0:
                res += str(digit)
        return res if res else "0"

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int m = num1.length(), n = num2.length();
        int[] result = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + result[p2];
                result[p1] += sum / 10;
                result[p2] = sum % 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int num : result) {
            if (sb.length() != 0 || num != 0) sb.append(num);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }

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> result(m + n, 0);
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + result[p2];
                result[p1] += sum / 10;
                result[p2] = sum % 10;
            }
        }
        string res;
        for (int num : result) {
            if (!res.empty() || num != 0) res += to_string(num);
        }
        return res.empty() ? "0" : res;
    }
};

Explanation

This solution uses the elementary multiplication algorithm with optimizations. Here's a detailed explanation of the algorithm:

Check if either num1 or num2 is "0". If so, return "0".
Initialize a result array of size m + n (where m and n are the lengths of num1 and num2) to store intermediate results.
Iterate through num1 and num2 from right to left, multiplying each pair of digits:
- Calculate the product of the current digits.
- Add this product to the appropriate positions in the result array.
- Handle carry-over by updating the previous position.
Convert the result array to a string, skipping leading zeros.
Return the final string result.

The time complexity is O(m*n), where m and n are the lengths of num1 and num2. The space complexity is O(m+n) for the result array.

Complexity

Time Complexity: O(m*n)
Space Complexity: O(m+n)

LeetSolved

Multiply Strings