leetcode/0043_Multiply_Strings.cpp at master · huochaitiantang/leetcode · GitHub

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<long long> format_num(string num){
        vector<long long> ans;
        // split as 8 bits (as 10 dec)
        for(int i = num.size() - 1; i >= 0; i -= 8){
            long long base = 1, val = 0;
            for(int j = 0; (j < 8) && (i - j >= 0); j++){
                val += (num[i - j] - '0') * base;
                base *= 10;
            }
            ans.push_back(val);
        }
        //reverse(ans.begin(), ans.end());
        return ans;
    }

    string multiply1(string num1, string num2) {
        int i, j;
        long long base, val, flag = 0;
        vector<long long> x1 = format_num(num1);
        vector<long long> x2 = format_num(num2);

        // multiply
        int n = x1.size() + x2.size() - 1;
        vector<long long> ans(n, 0);
        for(i = 0; i < x1.size(); i++){
            for(j = 0; j < x2.size(); j++){
                ans[i + j] += x1[i] * x2[j];
            }
        }

        vector<char> str;
        // tidy the ans, from low bit to high bit
        for(i = 0; i < n; i++){
            ans[i] += flag;
            cout << "ans " << i << " " << ans[i] << endl;
            flag = ans[i] / 100000000;
            ans[i] = ans[i] % 100000000;

            for(j = 0; j < 8; j++){
                str.push_back('0' + (ans[i] % 10));
                ans[i] = ans[i] / 10;
            }
        }
        if(flag > 0){
            for(j = 0; j < 8; j++){
                str.push_back('0' + (flag % 10));
                flag = flag / 10;
            }
        }

        // convert to the string ans
        string s = "";
        flag = 0;
        for(i = str.size() - 1; i >= 0; i--){
            if((flag == 0) && (str[i] == '0')) continue;
            flag = 1;
            s += str[i];
        }

        if(s.size() <= 0) return "0";
        else return s;
    }

    // split as one bit only
    string multiply(string num1, string num2) {
        int i, j, n1, n2, flag = 0;
        n1 = num1.size();
        n2 = num2.size();
        vector<int> ans(n1 + n2 - 1, 0);

        for(i = 0; i < n1; i++)
            for(j = 0; j < n2; j++)
                ans[i + j] += (num2[j] - '0') * (num1[i] - '0');

        string s = "";
        for(i = n1 + n2 - 2; i >= 0; i--){
            ans[i] += flag;
            flag = ans[i] / 10;
            ans[i] %= 10;
            s += (char)(ans[i] + '0');
        }
        while(flag > 0){
            s += (char)(flag % 10 + '0');
            flag /= 10;
        }
        while(s.back() == '0') s.pop_back();
        if(s.size() <= 0) return "0";
        reverse(s.begin(), s.end());

        return s;
    }
};

int main(){
    Solution solve;
    string num1 = "10000";
    string num2 = "0";

    cout << "Input: " << num1 << " x " << num2 << endl;
    cout << "Output: " << solve.multiply(num1, num2) << endl;

    return 0;
}