-
Notifications
You must be signed in to change notification settings - Fork 0
/
MultiplyStrings.cpp
75 lines (70 loc) · 1.62 KB
/
MultiplyStrings.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
*/
class Solution {
inline string addStr(string s1,string s2){
if(s1.size()==0||(s1.size()==1&&!s1[0]))
return s2;
else if(s2.size()==0||(s2.size()==1&&!s2[0]))
return s1;
int adv=0,p1,p2,tmp;
string res;
if(s1.size()>s2.size()){
res=s1;
s1=s2;
s2=res;
}
res="";
for(p1=0,p2=0;p1<s1.size();p1++,p2++){
tmp=(int)(s1[p1]-'0')+(int)(s2[p2]-'0')+adv;
res+=(char)('0'+tmp%10);
adv=tmp/10;
}
for(;p2<s2.size();p2++){
if(!adv)
res+=s2[p2];
else{
tmp=(int)(s2[p2]-'0')+adv;
res+=(char)('0'+tmp%10);
adv=tmp/10;
}
}
if(adv)
res+='1';
return res;
}
public:
string multiply(string num1, string num2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
assert(num1.size()!=0&&num2.size()!=0);
if((num1.size()==1&&num1[0]=='0')||(num2.size()==1&&num2[0]=='0'))
return "0";
string str="",str1;
int adv=0,tmp;
for(int i=num1.size()-1;i>=0;i--){
if(num1[i]!='0'){
str1="";adv=0;
for(int j=num1.size()-1;j>i;j--)
str1+='0';
for(int j=num2.size()-1;j>=0;j--){
tmp=(int)(num1[i]-'0')*(int)(num2[j]-'0')+adv;
str1+=(char)('0'+tmp%10);
adv=tmp/10;
}
while(adv){
str1+=(char)('0'+adv%10);
adv/=10;
}
str=addStr(str,str1);
}
}
for(int i=0,j=str.size()-1;i<j;i++,j--){ // reverse the result array;
str[i]^=str[j];
str[j]^=str[i];
str[i]^=str[j];
}
return str;
}
};