Blog Details

Multiply Strings – Leetcode Medium

1. Problem 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:

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

2. Solution

This problem evaluates how we manipulate big number math in programming. Before we start, let’s look at how we do multiplication by hand.

Step 1: Multiply each digit of string2 to string1.

#1. 4 * 7 = 28; temp = 8; carry = 2; sb.insert(0, 8); // sb=8
#2. 4 * 8 + 2 = 34; temp = 4; carry = 3; sb.insert(0, 4);// sb=48
#3. 4 * 1 + 3 = 7; temp = 7; carry = 0; sb.insert(0, 7);//sb= 748

#4. 5 * 7 = 35; temp = 5; carry = 3; // sb = 5;
#5. 5 * 8 + 3 = 43; temp = 3; carry = 4; // sb = 35
#6. 5 * 1 + 4 = 9; temp = 4; carry = 0; // sb = 935 
#7. append 0 to the end of sb; // sb = 9350

Step 2: Add each sb after calculation.

748 + 9350 = 10098

3. My Solution

class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) {
            return null;
        }
        if ("0".equals(num1) || "0".equals(num2) || "".equals(num1) || "".equals(num2)) {
            return "0";
        }
        ArrayList<String> tempEachResult = new ArrayList<String>();
        // #1 Multiply first
        // loop for num2
        for (int i = num2.length() - 1; i >= 0; i--) {
            StringBuffer resultOfEachNum2 = new StringBuffer();
            int carry = 0;
            // loop for num1
            for (int j = num1.length() - 1; j >= 0; j--) {
                int result = Character.getNumericValue(num2.charAt(i)) * Character.getNumericValue(num1.charAt(j))
                        + carry;
                // if it is the last digit of num1, no carry
                if (j == 0) {
                    resultOfEachNum2.insert(0, result);
                } else {
                    carry = result / 10;
                    resultOfEachNum2.insert(0, result % 10);
                }
            }
            // append 0s after the first multiplication
            for (int m = 0; m < num2.length() - 1 - i; m++) {
                resultOfEachNum2.append("0");
            }
            tempEachResult.add(resultOfEachNum2.toString());
        }




        // #2 Sum each result, maxLength of each string is the last element
        int sumCarry = 0;
        int maxLength = tempEachResult.get(tempEachResult.size() - 1).length();
        StringBuffer bfSumResult = new StringBuffer();
        // The index of last element.
        int lastIndex = 0;
        while(maxLength > 0) {
            int tempSum = 0;
            for (int i = 0; i < tempEachResult.size(); i++) {
                String tempEachNum = tempEachResult.get(i);
                int index = tempEachNum.length() - lastIndex - 1;
                if(index >= 0) {
                    tempSum += Character.getNumericValue(tempEachNum.charAt(index));
                }
            }
            tempSum += sumCarry;
            if(maxLength == 1) {
                bfSumResult.insert(0, tempSum);
            } else {
                bfSumResult.insert(0, tempSum % 10);
                sumCarry = tempSum / 10;
            }
            maxLength --;
            lastIndex ++;
        }
        System.out.println(bfSumResult.toString());
        return bfSumResult.toString();
    }
}