Multiply Strings

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.

C++:
01 void reverse(string& a)
02 {
03     int n=a.size();
04     for(int i=0;i<n/2;i++){
05         char tmp=a[i];
06         a[i]=a[n1i];
07         a[n1i]=tmp;
08     }
09 }
10 
11 string addString(string a, string b)
12 {
13     string small;
14     string large;
15     if(a.size()<=b.size()){
16         small=a;
17         large=b;
18     }else{
19         small=b;
20         large=a;
21     }
22     if(small.size()==0)
23         return large;
24     int n=small.size();
25     int m=large.size();
26     int carry=0;
27     string result;
28     for(int i=0;i<n;i++){
29         int p=small[n1i]‘0’;
30         int q=large[m1i]‘0’;
31         int t=carry+p+q;
32         if(t>9){
33             t=t10+‘0’;
34             carry=1;
35         }else{
36             t=t+‘0’;
37             carry=0;
38         }
39         result+=t;
40     }
41     for(int i=n;i<m;i++){
42         int p=large[m1i]‘0’;
43         int t=carry+p;
44         if(t>9){
45             t=t10+‘0’;
46             carry=1;
47         }else{
48             t=t+‘0’;
49             carry=0;
50         }
51         result+=t;
52     }
53 
54     if(carry==1){
55         result+=‘1’;
56     }
57     reverse(result);
58     return result;
59 }
60 
61 string multiplyChar(string num, char c)
62 {
63     int n=num.size();
64     if((n==0)||(c==‘0’))
65         return “0”;
66     int p=c‘0’;
67     int carry=0;
68     string result;
69     for(int i=n1;i>=0;i){
70         int q=num[i]‘0’;
71         int r=carry+p*q;
72         carry=r/10;
73         char d=r%10+‘0’;
74         result+=d;
75     }
76     if(carry>0){
77         char d=carry+‘0’;
78         result+=d;
79     }
80     reverse(result);
81     return result;
82 }
83 
84 string multiply(string num1, string num2)
85 {
86     string result;
87     int n=num1.size();
88     int m=num2.size();
89     for(int i=m1;i>=0;i){
90         char c=num2[i];
91         string tmp=multiplyChar(num1,c);
92         if(tmp!=“0”){
93             for(int j=0;j<m1i;j++)
94                 tmp+=‘0’;
95         }
96         result=addString(result,tmp);
97     }
98     return result;
99 }
Advertisements
This entry was posted in Number trick, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s