Posted on

Description

Submission

class Solution {
public:
    string add(string num1, string num2) {
        if(num1.empty()) return num2;
        if(num2.empty()) return num1;
        if(num1.size() > num2.size()) swap(num1, num2);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int carry = 0;
        string res = "";
        for(int i = 0; i < num1.size(); ++i) {
            int total = num1[i] + num2[i] - '0' * 2 + carry;
            carry = 0;
            if(total >= 10) {
                total -= 10;
                carry = 1;
            }
            res.push_back(total + '0');
        }
        string prefix = num2.substr(num1.size(), num2.size() - num1.size());
        reverse(prefix.begin(), prefix.end());
        if(carry == 1) prefix = add(prefix, "1");
        reverse(res.begin(), res.end());
        return prefix + res;
    }

    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") return "0";
        string res = "";
        for(int i = num2.size() - 1; i >= 0; --i) {
            string sub = "";
            int carry = 0;
            for(int j = num1.size() - 1; j >= 0; --j) {
                int total = (num2[i] - '0') * (num1[j] - '0') + carry;
                carry = total / 10;
                total %= 10;
                sub.push_back(total + '0');
            }
            if(carry > 0) sub.push_back(carry + '0');
            reverse(sub.begin(), sub.end());
            for(int k = i; k < num2.size() - 1; ++k) sub.push_back('0');
            res = add(res, sub);
        }
        return res;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *