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.

Understand why it is misplaced when multiplying. For example, the 48 obtained by multiplying 6 by 8 should be added with the wrong 54 obtained by multiplying 6 by 9, because 8 is a number in the tens place, which is equivalent to 80, so the staggered one is actually Need to add 0 at the end. One more thing to observe is 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, the number at position i in num1 is multiplied by the position in num2. If it is the number of j, then the positions of the two digits obtained are i+j and i+j+1. After you understand these, you can perform misplaced addition and accumulate the final result.

Since the multiplication starts from the ones digit, it 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 determine the positions p1 and p2 where the two digits after the multiplication are located. Since p2 is lower than p1, the two digits mul obtained are added to the position of p2 first, which may cause the number of 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 thing to do is to start from the high bit and store the number in the result res, remember that leading zeros should be skipped, and finally deal with the next corner case, that is, if the result res is empty, return “0”, otherwise return the result

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();
	    }
	}

}

All Problems

All Solutions