43. Multiply Strings
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.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Constraints:
1 <= num1.length, num2.length <= 200
num1
andnum2
consist of digits only.- Both
num1
andnum2
do not contain any leading zero, except the number0
itself.
Solution
Idea:
We are using regular mathematical vertical multiplication.
We loop from the end of both numbers, multiply the digits one at a time and save the carry in the next cell for the next iteration.
The loop at the end constructs the result string - we skip 0s at the beginning and add the numbers.
Time Complexity: O(mn)
Space Complexity: O(n+m)
class Solution {
public:
string multiply(string num1, string num2) {
if(num1=="0" || num2=="0"){
return "0";
}
vector<int>v(num1.size()+num2.size(),0);
for(int i=num1.size()-1; i>=0; i--){
for(int j=num2.size()-1; j>=0; j--){
v[i+j+1]+=(num1[i]-'0')*(num2[j]-'0');
v[i+j]+=v[i+j+1]/10;
v[i+j+1]%=10;
}
}
int i=0;
string ans="";
while(v[i]==0){
i++;
}
while(i<v.size()){
ans+=to_string(v[i]);
i++;
}
return ans;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.