LeetCode: Multiply Strings

Challenge Description

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

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

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

Approach with simulation of multiply operation

Let’s take a input as example, the result string’s length will be less than num1.length + num2.length.

And remember to strip the leading zero in result.

    123
     23
------
    369
   246
  ======
   2829

Time complexity: $O(MN)$ where M and N is the lengths of two numbers.

file:img/2020_02_05_leetcode-multiply-strings.org_20200205_125808.png

class Solution {
public:
  string multiply(string num1, string num2) {
    if(num1 == "0" || num2 == "0")
      return "0";

    vector<int> arr(num1.length() + num2.length(), 0);
    for(int i = num1.length()-1; i >= 0; i--){
      for(int j = num2.length()-1; j >= 0; j--){
        int multi = (num1[i]-'0') * (num2[j]-'0') + arr[i+j+1];
        arr[i+j+1] = multi % 10;
        arr[i+j] += multi / 10;
      }
    }
    int index= 0;
    string result = "";
    while(arr[index] == 0) index++;
    for(int i = index; i < arr.size(); i++)
      result += arr[i]+'0';

    return result;
  }
};

Join my Email List for more insights, It's Free!😋

← LeetCode: Pow(x, n) LeetCode: Container With Most Wa... →