SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given two non-negative integers represented as strings, return the product of the two numbers, also represented as a string. The input strings will not contain any leading zeroes except the number "0" itself.

Intuition

Multiplying large numbers can result in values that exceed the typical integer limits. Therefore, handling them as strings avoids overflow issues. By using elementary school multiplication techniques (similar to how we multiply numbers on paper), we can compute the product without directly converting the entire strings to numbers.

Approach

1. Check for Zero: If either of the input strings is "0", return "0" immediately since anything multiplied by zero is zero.
2. Prepare a Result Array: Create an array to hold the results of intermediate multiplications. The size of this array will be the sum of the lengths of the two numbers.
3. Multiply Digit by Digit:
   • Start from the least significant digit (the rightmost digit) of both numbers.
   • Multiply each digit of num1 with each digit of num2, and store the result in the corresponding position in the result array.
   • Accumulate the results while handling carry-over to the next significant position.
4. Convert Result Array to String:
   • Convert the result array back into a string, skipping leading zeroes.
   • If the result is empty after removing zeroes, return "0".
5. Edge Cases: Handle cases where the result is zero or where the input strings are very short (e.g., "1" or "9").

Complexity

Time Complexity:

O(n * m) where n and m are the lengths of the two input strings. This is because each digit of the first number is multiplied by each digit of the second number.

Space Complexity

O(n + m) to store the result of the multiplication in an array, where n and m are the lengths of the two input strings.

Code

C++

class Solution {
public:
    std::string multiply(std::string num1, std::string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        std::vector<int> result(num1.size() + num2.size(), 0);

        for (int i = num1.size() - 1; i >= 0; --i) {
            for (int j = num2.size() - 1; j >= 0; --j) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int sum = mul + result[i + j + 1];

                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }

        std::string resultStr;
        for (int num : result) {
            if (!(resultStr.empty() && num == 0)) {
                resultStr.push_back(num + '0');
            }
        }
        return resultStr.empty() ? "0" : resultStr;
    }
};

Python

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        return str(int(num1) * int(num2))

Java

import java.math.BigInteger;

class Solution {
    public String multiply(String num1, String num2) {
        BigInteger b1 = new BigInteger(num1);
        BigInteger b2 = new BigInteger(num2);
        BigInteger result = b1.multiply(b2);
        return result.toString();
    }
}

JavaScript

var multiply = function (num1, num2) {
    
    let b = BigInt(num1) * BigInt(num2)
    return String(b)
};