package com.freetymekiyan.algorithms.level.medium;

/**
 * Given two numbers represented as strings, return multiplication of the numbers as a string.
 * <p>
 * Note:
 * The numbers can be arbitrarily large and are non-negative.
 * Converting the input string to integer is NOT allowed.
 * You should NOT use internal library such as BigInteger.
 * <p>
 * Company Tags: Facebook, Twitter
 * Tags: Math, String
 * Similar Problems: (M) Add Two Numbers, (E) Plus One, (E) Add Binary, (E) Add Strings
 */
public class MultiplyStrings {

    /**
     * Math. String.
     * How to do multiplication?
     * Start from right to left, multiply each pair of digits, and add them together.
     * Result num1[i] * num2[j] will be placed at i + j and i + j + 1.
     * Mimic this process.
     * Special cases:
     * 1) If one of the strings is null, return empty.
     * 2) If one of the strings is zero, return zero.
     */
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) {
            return "";
        }
        if ("0".equals(num1) || "0".equals(num2)) { // If one number is 0.
            return "0";
        }
        int m = num1.length(), n = num2.length();
        int[] product = new int[m + n]; // Length is at most m + n.
        // Pick one digit from one number, multiply with each digit in the other number.
        for (int i = m - 1; i >= 0; i--) { // From right to left, from lower significant digit to higher.
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1; // p1 is a more significant digit than p2.
                int sum = mul + product[p2];
                product[p1] += sum / 10; // Carry.
                product[p2] = sum % 10;
            }
        }

        StringBuilder ans = new StringBuilder();
        for (int p : product) {
            if (p != 0 || ans.length() != 0) { // Not zero, or not empty.
                ans.append(p);
            }
        }
        return ans.toString();
    }
}

@@ -49,16 +49,47 @@
 m;%0A%0A/**%0A
+ * 43. Multiply Strings%0A * %3Cp%3E%0A
  * Given
@@ -1493,24 +1493,66 @@
  to higher.%0A
+            int x = num1.charAt(i) - '0';%0A
             
@@ -1616,30 +1616,9 @@
 l = 
-(num1.charAt(i) - '0')
+x
  * (
@@ -1660,162 +1660,87 @@
     
-int p1 = i + j, p2 = i + j + 1; // p1 is a more significant digit than p2.%0A                int sum = mul + product%5Bp2%5D;%0A                product%5Bp1%5D += sum
+product%5Bi + j + 1%5D += mul;%0A                product%5Bi + j%5D += product%5Bi + j + 1%5D
  / 1
@@ -1780,23 +1780,81 @@
 uct%5B
-p2
+i + j + 1
 %5D 
+%25
 = 
-sum %25 10;
+10; // i + j + 1 will cover every digit and make them %3C 10.
 %0A   
@@ -1897,18 +1897,18 @@
 Builder 
-an
+re
 s = new 
@@ -1982,18 +1982,18 @@
 != 0 %7C%7C 
-an
+re
 s.length
@@ -2012,28 +2012,117 @@
 / No
-t 
+n-
 zero
-, or not empty
+ should definitely be in result. If something is already in result, everything after should be appended
 .%0A  
@@ -2135,18 +2135,18 @@
         
-an
+re
 s.append
@@ -2189,18 +2189,18 @@
  return 
-an
+re
 s.toStri
@@ -2212,9 +2212,8 @@
 %0A    %7D%0A%7D
-%0A

update 43. Multiply Strings