Question

Formatted question description: https://leetcode.ca/all/43.html

43. Multiply Strings

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.

Algorithm

The length of the product obtained by multiplying two numbers does not actually exceed the sum of the lengths of the two numbers. If the length of num1 is m and the length of num2 is n, the length of num1 * num2 will not exceed m+n.

To understand why it is misplaced when multiplying, consider the example of 6 multiplied by 8, which produces 48. If we incorrectly add the result of multiplying 6 by 9, which is 54, it is because 8 is a number in the tens place, which is equivalent to 80. So the result in the ones place actually needs a 0 at the end. It is also important to observe that if two digits at any position in num1 and num2 are multiplied, the position of the two digits obtained in the final result is determined. For example, if the number at position i in num1 is multiplied by the number at position j in num2, then the positions of the two digits obtained are i+j and i+j+1. Once these concepts are understood, misplaced addition can be performed and the final result can be accumulated.

To implement this algorithm, the multiplication starts from the ones digit and traverses from the end of the num1 and num2 strings to extract the characters at the corresponding positions respectively, convert them to integers, and multiply them. Then the positions p1 and p2 where the two digits after the multiplication are located are determined. Since p2 is lower than p1, the two digits obtained are added to the position of p2 first. This may cause the number at position p2 to be greater than 9, so the number in the ten’s place must be added to the high-order p1, and only the remainder is left in the p2 position, so that the number in each place becomes one. The next step is to store the number in the result res starting from the high bit, while skipping any leading zeros. Finally, the corner case of an empty result res is handled by returning “0”, otherwise the result is returned.

Code

Java

import java.math.BigInteger;
import java.util.Arrays;

public class Multiply_Strings {

	public static void main(String[] args) {

		int n = '9' - '0';
		System.out.println(n);

		Multiply_Strings out = new Multiply_Strings();
		Solution s = out.new Solution();

		System.out.println(s.multiply("123", "456"));

	}


	public class Solution {
	    public String multiply(String num1, String num2) {

	    	// validation as to according to description, should also check length<110 and no leading zero
	        if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) {
	            return "";
	        }

	        // @note: proof: 999 * 999 = (1000 - 1)^2 < 1000^2=1000000
	        // i.e.: n1*n2 < 10^(len1+len2)  <=>  n1*n2 <= 999...99(length=len1+len2)
	        int[] result = new int[num1.length() + num2.length()];

	        // @note: reverse is better for store in results, or else reverse direction is annoying
	        String n1 = new StringBuilder(num1).reverse().toString();
	        String n2 = new StringBuilder(num2).reverse().toString();

	        int carry = 0;
	        int i = 0; // @note: for final check
	        int j = 0; // @note: for final check
	        for ( ; i < n1.length(); i++) {

	        	carry = 0; // @note: i missed this one, every out loop should update carry!
	            int d1 = n1.charAt(i) - '0'; // digit of n1


	            // for (; j < n2.length(); j++) { // @note: here j is not re-set to 0 in another i-loop
	            								  //  that's why I like while() !!!
	            for ( ; j < n2.length(); j++) {

	                // first calculate this d1*n2
	                int d2 = n2.charAt(j) - '0';

	                int single = d1 * d2;
	                int addCarry = single + carry;

	                // add up to result array
	                // i is also the indicator of start index in result array
	                result[i + j] += addCarry;

	                // @note: careful using if-else, and if carry<10 it's not updated
	                // if (single >= 10) {
	                //     carry += result[i + j] / 10;
	                //     single = result[i + j] % 10;
	                // }
	                carry = result[i + j] / 10;
	                result[i + j] = result[i + j] % 10;

	            }

	            // @note: outside inner loop, there should be a final check (not outside both for-loop)
	            // eg.123*456
	            if (carry > 0) { // j is ++ already
	            	result[i + j] = carry;
	            }
	        }

	        // restore as string
	        String m = "";
	        for (i = 0; i < result.length; i++) {
	            m = result[i] + m;
	        }

	        while (m.length() > 1 && m.charAt(0) == '0') {
	            m = m.substring(1);
	        }

	        return m;
	    }
	}


	// but theoretical still overflow possibility
	public class Solution_big_integer {
	    public String multiply(String num1, String num2) {

	        BigInteger a = new BigInteger(num1);
	        BigInteger b = new BigInteger(num2);

	        a = a.multiply(b);

	        return a.toString();
	    }
	}

}

// OJ: https://leetcode.com/problems/multiply-strings/
// Time: O(MN)
// Space: O(M + N)
class Solution {
    string mul(const string &a, int n, int shift) {
        if (n == 0 || a == "0") return "0";
        int carry = 0;
        string ans;
        for (int N = a.size(), i = N - 1; i >= 0 || carry;) {
            if (i >= 0) carry += (a[i--] - '0') * n;
            ans += carry % 10 + '0';
            carry /= 10;
        }
        reverse(begin(ans), end(ans));
        while (shift--) ans += '0';
        return ans;
    }
    string add(string a, string b) {
        if (a == "0") return b;
        if (b == "0") return a;
        string ans;
        for (int i = a.size() - 1, j = b.size() - 1, carry = 0; i >= 0 || j >= 0 || carry; ) {
            if (i >= 0) carry += a[i--] - '0';
            if (j >= 0) carry += b[j--] - '0';
            ans += carry % 10 + '0';
            carry /= 10;
        }
        reverse(begin(ans), end(ans));
        return ans;
    }
public:
    string multiply(string a, string b) {
        string ans = "0";
        for (int i = 0, N = b.size(); i < N; ++i) {
            ans = add(ans, mul(a, b[N - 1 - i] - '0', i));
        }
        return ans;
    }
};

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        m, n = len(num1), len(num2)
        arr = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            a = int(num1[i])
            for j in range(n - 1, -1, -1):
                b = int(num2[j])
                arr[i + j + 1] += a * b
        for i in range(m + n - 1, 0, -1):
            arr[i - 1] += arr[i] // 10
            arr[i] %= 10
        i = 0 if arr[0] else 1
        return "".join(str(x) for x in arr[i:])

############

class Solution(object):
  def multiply(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    ans = [0] * (len(num1) + len(num2))
    for i, n1 in enumerate(reversed(num1)):
      for j, n2 in enumerate(reversed(num2)):
        ans[i + j] += int(n1) * int(n2)
        ans[i + j + 1] += ans[i + j] / 10
        ans[i + j] %= 10
    while len(ans) > 1 and ans[-1] == 0:
      ans.pop()
    return "".join(map(str, ans[::-1]))

43 - Multiply Strings

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions