原题

LintCode 656. Big Integer multiplication

Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2

Example

• The length of both num1 and num2 is < 110.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

解题

高精度乘法

代码

class Solution {
public:
    /*
    * @param num1: a non-negative integers
    * @param num2: a non-negative integers
    * @return: return product of num1 and num2
    */
    string multiply(string &num1, string &num2) {
        // write your code here
        if (num1 == "0" || num2 == "0") return "0";
        int n = num1.size() + num2.size();
        int *res = new int[n];
        for (int i = 0; i < n; i++) res[i] = 0;
        if (num1.length() < num2.length()) swap(num1, num2);
        for (int i = num1.size() - 1; i >= 0; i--) {
            for (int j = num2.size() - 1; j >= 0; j--) {
                res[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        for (int i = n - 1; i > 0; i--) {
            res[i - 1] += res[i] / 10;
            res[i] %= 10;
        }
        string ans;
        for (int i = 0; i < n; i++) {
            if (res[i] == 0 && ans.empty()) continue;
            ans += char(res[i] + '0');
        }
        return ans;
    }
};