Algorithm to Multiply Two Big Integers (String)

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 smaller than 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.

Using BigInteger to Multiply Two BigInteger in Java

Using BigInteger Library to solve this problem is trivial.

1
2
3
4
5
6
7
8
9

import java.math.BigInteger;
 
public class Solution {
    public String multiply(String num1, String num2) {
        BigInteger a = new BigInteger(num1);
        BigInteger b = new BigInteger(num2);
        return a.multiply(b).toString();
    }
}

import java.math.BigInteger;

public class Solution {
    public String multiply(String num1, String num2) {
        BigInteger a = new BigInteger(num1);
        BigInteger b = new BigInteger(num2);
        return a.multiply(b).toString();
    }
}

Implement the High Accuracy Multiplication

Since the two numbers are stored in strings, we can simulate the multiplication process and store the results in a string. We can perform a O(N^2) loop to multiple two digits from each number and store the results in corresponding position. Also, we need to take care of the carry.

We also need to remove the leading zeros in the final string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] ans = new int[m + n + 1];
        // Arrays.fill(ans, 0);
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                ans[i + j] += (num1.charAt(m - i - 1) - '0') * (num2.charAt(n - j - 1) - '0');
                ans[i + j + 1] += ans[i + j] / 10;
                ans[i + j] %= 10;
            }
        }
        StringBuilder res = new StringBuilder();
        int i = m + n - 1;
        // skip leading zeros
        while ((i > 0) && (ans[i] == 0)) -- i;
        while (i >= 0) {
            res.append((char)(48 + ans[i]));
            -- i;
        }
        return res.toString();
    }
}

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] ans = new int[m + n + 1];
        // Arrays.fill(ans, 0);
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                ans[i + j] += (num1.charAt(m - i - 1) - '0') * (num2.charAt(n - j - 1) - '0');
                ans[i + j + 1] += ans[i + j] / 10;
                ans[i + j] %= 10;
            }
        }
        StringBuilder res = new StringBuilder();
        int i = m + n - 1;
        // skip leading zeros
        while ((i > 0) && (ans[i] == 0)) -- i;
        while (i >= 0) {
            res.append((char)(48 + ans[i]));
            -- i;
        }
        return res.toString();
    }
}

The numbers/digits are multiplied from right to left. Thus we can reverse the strings or use the index to refer to the correct digit.

See also: Teaching Kids Programming – High Accuracy Multiplication Algorithm (Multiply Strings)

–EOF (The Ultimate Computing & Technology Blog) —