Coder's Cat

LeetCode: Multiply Strings

2020-02-05

Challenge Description

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.

Approach with simulation of multiply operation

Let’s take a input as example, the result string’s length will be less than num1.length + num2.length.

And remember to strip the leading zero in result.

    123
23
------
369
246
======
2829

Time complexity: $O(MN)$ where M and N is the lengths of two numbers.

file:img/2020_02_05_leetcode-multiply-strings.org_20200205_125808.png

class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")
return "0";

vector<int> arr(num1.length() + num2.length(), 0);
for(int i = num1.length()-1; i >= 0; i--){
for(int j = num2.length()-1; j >= 0; j--){
int multi = (num1[i]-'0') * (num2[j]-'0') + arr[i+j+1];
arr[i+j+1] = multi % 10;
arr[i+j] += multi / 10;
}
}
int index= 0;
string result = "";
while(arr[index] == 0) index++;
for(int i = index; i < arr.size(); i++)
result += arr[i]+'0';

return result;
}
};