2013.12.15 04:07

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.

Solution:

　　I just did a digit-by-digit multiplication. There seemed to be a very complicated O(n * log(n)) solution, using Fast Fourier Transformation.

　　Here is the link to that solution, if you are eager to dip into it: 

　　Also there is an exercise problem on "", I'll paste my O(n * log(n)) solution here when I understand how it works (^_^)

　　Time complexity is O(n^2), where n is the length of the array. Space complexity is O(n), since storing the array requires O(n) space.

Accepted code:

1 // 1CE, 1AC, nice performance 2 class Solution { 3 public: 4     string multiply(string num1, string num2) { 5         // IMPORTANT: Please reset any member data you declared, as 6         // the same Solution instance will be reused for each test case. 7         if(num1 == "0" || num2 == "0"){ 8             return "0"; 9         }10         11         int *a1, *a2, *a3;12         int max_len, n;13         char *buf;14 15         max_len = num1.length() + num2.length() + 5;16         a1 = new int[max_len];17         a2 = new int[max_len];18         a3 = new int[max_len];19         buf = new char[max_len];20         // 1CE here, declaration for $j missing21         int i, j;22         23         for(i = 0; i < max_len; ++i){24             a1[i] = a2[i] = a3[i] = 0;25             buf[i] = 0;26         }27         28         n = num1.length();29         for(i = 0; i <= n - 1; ++i){30             a1[n - 1 - i] = num1[i] - '0';31         }32         33         n = num2.length();34         for(i = 0; i <= n - 1; ++i){35             a2[n - 1 - i] = num2[i] - '0';36         }37         38         for(i = 0; i < max_len; ++i){39             if(a1[i] == 0){40                 continue;41             }42             for(j = 0; i + j < max_len; ++j){43                 a3[i + j] += a1[i] * a2[j];44             }45         }46         47         for(i = 0; i < max_len - 1; ++i){48             a3[i + 1] += a3[i] / 10;49             a3[i] %= 10;50         }51         a3[max_len - 1] %= 10;52         i = max_len - 1;53         while(i >=0 && a3[i] == 0){54             --i;55         }56         57         if(i < 0){58             sprintf(buf, "0");59         }else{60             j = 0;61             while(i >= 0){62                 buf[j++] = a3[i--] + '0';63             }64         }65         66         string res = string(buf);67         68         delete[] a1;69         delete[] a2;70         delete[] a3;71         delete[] buf;72         return res;73     }74 };