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++:
001 string shift(string s,int t)
002 {
003     if(s==“0”)
004         return s;
005     for(int i=0;i<t;i++)
006         s=s+‘0’;
007     return s;
008 }
009 string multiplyChar(string s, char c)
010 {
011     if((c==‘0’)||(s==“0”))
012         return “0”;
013     if(c==‘1’)
014         return s;
015     int n=s.size()1;
016     int carry=0;
017     string result;
018     stack<char> A;
019     while(n>=0)
020     {
021         int p=s[n]‘0’;
022         int q=c‘0’;
023         int tmp=p*q+carry;
024         carry=tmp/10;
025         tmp=tmpcarry*10;
026         A.push(tmp+‘0’);
027     }
028     if(carry>0)
029         A.push(carry+‘0’);
030     while(!A.empty())
031     {
032         char tmp=A.top();
033         A.pop();
034         result+=tmp;
035     }
036     return result;
037 }
038 string add(string s, string t)
039 {
040     stack<char> A;
041     string result;
042     int n=s.size()1;
043     int m=t.size()1;
044     int carry=0;
045     while((n>=0)&&(m>=0))
046     {
047         int p=s[n]‘0’;
048         int q=t[m]‘0’;
049         int sum=p+q+carry;
050         if(sum>=10)
051         {
052             carry=1;
053             char c=sum10+‘0’;
054             A.push(c);
055         }
056         else
057         {
058             carry=0;
059             char c=sum+‘0’;
060             A.push(c);
061         }
062     }
063     while((n>=0)||(m>=0))
064     {
065         int p=n>=0?s[n]‘0’:t[m]‘0’;
066         int sum=p+carry;
067         if(sum>=10)
068         {
069             carry=1;
070             char c=sum10+‘0’;
071             A.push(c);
072         }
073         else
074         {
075             carry=0;
076             char c=sum+‘0’;
077             A.push(c);
078         }
079     }
080     if(carry==1)
081         A.push(‘1’);
082     while(!A.empty())
083     {
084         char tmp=A.top();
085         A.pop();
086         result+=tmp;
087     }
088     return result;
089 }
090 class Solution {
091 public:
092     string multiply(string num1, string num2) {
093         // Start typing your C/C++ solution below
094         // DO NOT write int main() function
095         string result;
096         int n=num2.size();
097         for(int i=n1;i>=0;i)
098         {
099             char c=num2[i];
100             string tmp=multiplyChar(num1,c);
101             tmp=shift(tmp,n1i);
102             result=add(result,tmp);
103         }
104         return result;
105     }
106 };
Advertisements
This entry was posted in Number trick, Stack and Queue, 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