This is the 24th day of my participation in the wenwen Challenge

Topic describes

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

Example 1:

Input: num1 = "2", num2 = "3" output: "6"Copy the code

Example 2:

Input: num1 = "123", num2 = "456" Output: "56088"Copy the code

Description:

  • num1 和 num2The length is less than 110.
  • num1 和 num2Contains only the numbers 0-9.
  • num1 和 num2None begins with a zero, except the number 0 itself.
  • You cannot use any of the library’s large number types (e.gBigInteger) or simply convert the input to an integer.

Their thinking

If either num1 or num2 is 000, 000 is simply returned as the result.

If neither num1 nor num2 is zero, the product can be computed by simulating “vertical multiplication”. Iterate over the multiplier from right to left, multiplying each bit of the multiplier by its victim to get the corresponding result, and adding the result each time. In this case, the multiplicator is num1, and the multiplier is num2.

Note that all num2 bits except the lowest digit need to be supplemented with 0

code

C + + code

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        string ans = "0";
        int m = num1.size(), n = num2.size(a);for (int i = n - 1; i >= 0; i--) {
            string curr;
            int add = 0;
            for (int j = n - 1; j > i; j--) {
                curr.push_back(0);
            }
            int y = num2.at(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.at(j) - '0';
                int product = x * y + add;
                curr.push_back(product % 10);
                add = product / 10;
            }
            while(add ! =0) {
                curr.push_back(add % 10);
                add /= 10;
            }
            reverse(curr.begin(), curr.end());
            for (auto &c : curr) {
                c += '0';
            }
            ans = addStrings(ans, curr);
        }
        return ans;
    }

    string addStrings(string &num1, string &num2) {
        int i = num1.size() - 1, j = num2.size() - 1, add = 0;
        string ans;
        while (i >= 0 || j >= 0|| add ! =0) {
            int x = i >= 0 ? num1.at(i) - '0' : 0;
            int y = j >= 0 ? num2.at(j) - '0' : 0;
            int result = x + y + add;
            ans.push_back(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        reverse(ans.begin(), ans.end());
        for (auto &c: ans) {
            c += '0';
        }
        returnans; }};Copy the code

Python3 code

class Solution:
    def multiply(self, num1: str, num2: str) - >str:
        if num1 == "0" or num2 == "0":
            return "0"
        
        ans = "0"
        m, n = len(num1), len(num2)
        for i in range(n - 1, -1, -1):
            add = 0
            y = int(num2[i])
            curr = ["0"] * (n - i - 1)
            for j in range(m - 1, -1, -1):
                product = int(num1[j]) * y + add
                curr.append(str(product % 10))
                add = product // 10
            if add > 0:
                curr.append(str(add))
            curr = "".join(curr[::-1])
            ans = self.addStrings(ans, curr)
        
        return ans
    
    def addStrings(self, num1: str, num2: str) - >str:
        i, j = len(num1) - 1.len(num2) - 1
        add = 0
        ans = list(a)while i >= 0 or j >= 0 oradd ! =0:
            x = int(num1[i]) if i >= 0 else 0
            y = int(num2[j]) if j >= 0 else 0
            result = x + y + add
            ans.append(str(result % 10))
            add = result // 10
            i -= 1
            j -= 1
        return "".join(ans[::-1])
Copy the code