LeetCode

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: http://hi.baidu.com/aekdycoin/item/0096b386bfadfd2e100ef3dc

　　Also there is an exercise problem on "Introduction to Algorithms", 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 missing
21         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 };