43. Multiply Strings

Medium

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.

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

Examples

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

Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def multiply(num1: str, num2: str) -> str:
    if num1 == "0" or num2 == "0":
        return "0"
    
    # Initialize result array
    result = [0] * (len(num1) + len(num2))
    
    # Multiply each digit
    for i in range(len(num1)-1, -1, -1):
        for j in range(len(num2)-1, -1, -1):
            digit1 = ord(num1[i]) - ord('0')
            digit2 = ord(num2[j]) - ord('0')
            product = digit1 * digit2
            
            # Add to position
            pos1 = i + j
            pos2 = i + j + 1
            total = result[pos2] + product
            
            result[pos2] = total % 10
            result[pos1] += total // 10
    
    # Convert to string
    result_str = ""
    start = 0
    while start < len(result) and result[start] == 0:
        start += 1
    
    return "".join(map(str, result[start:])) if start < len(result) else "0"

Java Solution


class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        
        int[] result = new int[num1.length() + num2.length()];
        
        // Multiply each digit
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int digit1 = num1.charAt(i) - '0';
                int digit2 = num2.charAt(j) - '0';
                int product = digit1 * digit2;
                
                int pos1 = i + j;
                int pos2 = i + j + 1;
                int total = result[pos2] + product;
                
                result[pos2] = total % 10;
                result[pos1] += total / 10;
            }
        }
        
        // Convert to string
        StringBuilder sb = new StringBuilder();
        boolean leadingZero = true;
        for (int digit : result) {
            if (digit != 0 || !leadingZero) {
                leadingZero = false;
                sb.append(digit);
            }
        }
        
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

C++ Solution


class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        
        vector result(num1.length() + num2.length(), 0);
        
        // Multiply each digit
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int digit1 = num1[i] - '0';
                int digit2 = num2[j] - '0';
                int product = digit1 * digit2;
                
                int pos1 = i + j;
                int pos2 = i + j + 1;
                int total = result[pos2] + product;
                
                result[pos2] = total % 10;
                result[pos1] += total / 10;
            }
        }
        
        // Convert to string
        string output = "";
        bool leadingZero = true;
        for (int digit : result) {
            if (digit != 0 || !leadingZero) {
                leadingZero = false;
                output += to_string(digit);
            }
        }
        
        return output.empty() ? "0" : output;
    }
};

JavaScript Solution


/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    if (num1 === "0" || num2 === "0") {
        return "0";
    }
    
    const result = new Array(num1.length + num2.length).fill(0);
    
    // Multiply each digit
    for (let i = num1.length - 1; i >= 0; i--) {
        for (let j = num2.length - 1; j >= 0; j--) {
            const digit1 = num1.charCodeAt(i) - '0'.charCodeAt(0);
            const digit2 = num2.charCodeAt(j) - '0'.charCodeAt(0);
            const product = digit1 * digit2;
            
            const pos1 = i + j;
            const pos2 = i + j + 1;
            const total = result[pos2] + product;
            
            result[pos2] = total % 10;
            result[pos1] += Math.floor(total / 10);
        }
    }
    
    // Convert to string
    while (result[0] === 0) {
        result.shift();
    }
    
    return result.length ? result.join('') : "0";
};

C# Solution


public class Solution {
    public string Multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        
        int[] result = new int[num1.Length + num2.Length];
        
        // Multiply each digit
        for (int i = num1.Length - 1; i >= 0; i--) {
            for (int j = num2.Length - 1; j >= 0; j--) {
                int digit1 = num1[i] - '0';
                int digit2 = num2[j] - '0';
                int product = digit1 * digit2;
                
                int pos1 = i + j;
                int pos2 = i + j + 1;
                int total = result[pos2] + product;
                
                result[pos2] = total % 10;
                result[pos1] += total / 10;
            }
        }
        
        // Convert to string
        StringBuilder sb = new StringBuilder();
        bool leadingZero = true;
        foreach (int digit in result) {
            if (digit != 0 || !leadingZero) {
                leadingZero = false;
                sb.Append(digit);
            }
        }
        
        return sb.Length == 0 ? "0" : sb.ToString();
    }
}

Complexity Analysis

Solution Explanation

This solution implements multiplication of large numbers using the elementary school multiplication method. Here's how it works:

Key points: