algoadvance

Leetcode 43. Multiply Strings

Problem Statement

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

Example 1:

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

Example 2:

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

Note:

  1. The length of both num1 and num2 is less than 110.
  2. Both num1 and num2 contain only digits 0-9.
  3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Clarifying Questions

  1. Leading Zeros: Can the input have leading zeros?
    • Based on the problem statement, only “0” might be a case of leading zero.
  2. Output format: Should the output string handle edge cases, such as when the product is “0”?
    • Yes, handle and return “0” correctly if the product is zero.

Strategy

  1. Initialization:
    • Use an array result to store intermediate results, with size num1.size() + num2.size() because the maximum length of the product can be this size.
  2. Multiplication:
    • Perform multiplication digit by digit, similar to the manual multiplication method.
    • Traverse num1 from the end to the beginning and for each digit do the same with num2.
  3. Sum products:
    • Store intermediate results in appropriate positions in the result array.
    • Calculate the carry and add it to the next position.
  4. Format the result:
    • Convert the result array to string, skipping leading zeros.
  5. Edge cases:
    • If the numbers are zero, immediately return “0”.

Code

Here is the C++ implementation:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::string multiply(std::string num1, std::string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    
    int m = num1.size();
    int n = num2.size();
    std::vector<int> result(m + n, 0);
    
    // Reverse both numbers to facilitate multiplication from least significant digit
    std::reverse(num1.begin(), num1.end());
    std::reverse(num2.begin(), num2.end());
    
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            result[i + j] += mul;
            
            // Carry handling
            result[i + j + 1] += result[i + j] / 10;
            result[i + j] %= 10;
        }
    }
    
    // Find the first non-zero digit from the end
    int i = m + n - 1;
    while (i >= 0 && result[i] == 0) --i;
    
    // Construct the final result string
    std::string finalResult;
    while (i >= 0) {
        finalResult += std::to_string(result[i]);
        --i;
    }
    
    return finalResult;
}

// Main function for testing
int main() {
    std::string num1 = "123";
    std::string num2 = "456";
    std::cout << multiply(num1, num2) << std::endl; // Output should be "56088"
    return 0;
}

Time Complexity

This solution efficiently multiplies two arbitrary-length numbers represented as strings without converting them directly to integers, adhering to the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI