Solution For 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:

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

Solution:

One approach to solve the problem is to simulate the multiplication process we use in our school. The idea is to multiply each digit of the second number (i.e., num2) with each digit of the first number (i.e., num1) and add the results at the appropriate positions to get the final product. We can store the result in a list and then convert it to a string.

Algorithm:
1. Initialize a list res with length (m+n) and fill it with 0’s where m and n are the length of num1 and num2 respectively.
2. Reverse both strings (num1 and num2) to start from the least significant digit.
3. Traverse num1 from right to left and multiply each digit with num2 from right to left. The product will have two digits, and we can keep the least significant digit at the current position and carry the higher digit to the next position.
4. After completing the first multiplication, we will have m+n-1 digits in the result. If there is a carry at the last position, add it to the next position.
5. Repeat the same process for all digits of num1.
6. Remove the leading zeros from the result, and if the result is empty, return “0”.
7. Convert the result list to a string and return it.

Time Complexity: O(m*n), where m and n are the lengths of num1 and num2 respectively, as we need to multiply each digit of num1 with each digit of num2.

Space Complexity: O(m+n), for the result list.

Python Code:

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

    m, n = len(num1), len(num2)
    res = [0]*(m+n)

    num1 = num1[::-1]
    num2 = num2[::-1]

    for i in range(m):
        carry = 0
        for j in range(n):
            prod = int(num1[i])*int(num2[j])
            pos = i+j
            res[pos] += (prod%10 + carry)
            carry = prod//10 + res[pos]//10
            res[pos] = res[pos]%10

        if carry:
            res[i+j+1] += carry

    while len(res)>1 and res[-1]==0:
        res.pop()

    return "".join(map(str, res[::-1])) if res else "0"

Step by Step Implementation For Multiply Strings

public class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = 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 + pos[p2];
                
                pos[p1] += sum / 10;
                pos[p2] = (sum) % 10;
            }
        }  
        
        StringBuilder sb = new StringBuilder();
        for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

def multiply(num1, num2):
    
    # Base cases
    if num1 == "0" or num2 == "0":
        return "0"
    
    # num1 and num2 are not zero
    
    # Initialize result
    result = [0] * (len(num1) + len(num2))
    
    # Go from right to left in num1
    for i in range(len(num1) - 1, -1, -1):
        
        # Go from right to left in num2
        for j in range(len(num2) - 1, -1, -1):
            
            # Multiply digits and place them in the correct position
            # in the result
            result[i + j + 1] += int(num1[i]) * int(num2[j])
            
            # Handle carry
            if result[i + j + 1] >= 10:
                result[i + j] += result[i + j + 1] // 10
                result[i + j + 1] %= 10
    
    # Convert result to string
    return "".join(map(str, result))

var multiply = function(num1, num2) {
    // your code goes here
};

class Solution {
public:
    string multiply(string num1, string num2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len1 = num1.size(), len2 = num2.size();
        string res(len1 + len2, '0');
        for(int i = len1 - 1; i >= 0; --i) {
            int carry = 0;
            for(int j = len2 - 1; j >= 0; --j) {
                int tmp = (res[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
                res[i + j + 1] = tmp % 10 + '0';
                carry = tmp / 10;
            }
            res[i] += carry;
        }
        size_t startpos = res.find_first_not_of("0");
        if(string::npos != startpos) {
            return res.substr(startpos);
        }
        return "0";
    }
};

public class Solution {
    public string Multiply(string num1, string num2) {
        // convert strings to arrays of characters for easier manipulation
        char[] n1 = num1.ToCharArray();
        char[] n2 = num2.ToCharArray();
        
        // create a new array to store the result with an extra element for the carry
        int[] result = new int[n1.Length + n2.Length];
        
        // iterate through each digit in num1
        for(int i = n1.Length - 1; i >= 0; i--) {
            // iterate through each digit in num2
            for(int j = n2.Length - 1; j >= 0; j--) {
                // multiply the digits and store the result in the appropriate index of the result array
                // the appropriate index is calculated by taking the sum of the current indices in num1 and num2 and subtracting it from the end of the result array
                result[i + j + 1] += (n1[i] - '0') * (n2[j] - '0');
            }
        }
        
        // iterate through result array
        for(int i = result.Length - 1; i > 0; i--) {
            // if the current element is greater than 9, carry the 1
            if(result[i] > 9) {
                result[i - 1] += result[i] / 10;
                result[i] %= 10;
            }
        }
        
        // convert result array to string
        string output = string.Join("", result);
        
        // remove leading 0
        return output.TrimStart('0');
    }
}