AC solution in Java with explanation


  • 72
    L
    public class Solution {
        public String multiply(String num1, String num2) {
            int n1 = num1.length(), n2 = num2.length();
            int[] products = new int[n1 + n2];
            for (int i = n1 - 1; i >= 0; i--) {
                for (int j = n2 - 1; j >= 0; j--) {
                    int d1 = num1.charAt(i) - '0';
                    int d2 = num2.charAt(j) - '0';
                    products[i + j + 1] += d1 * d2;
                }
            }
            int carry = 0;
            for (int i = products.length - 1; i >= 0; i--) {
                int tmp = (products[i] + carry) % 10;
                carry = (products[i] + carry) / 10;
                products[i] = tmp;
            }
            StringBuilder sb = new StringBuilder();
            for (int num : products) sb.append(num);
            while (sb.length() != 0 && sb.charAt(0) == '0') sb.deleteCharAt(0);
            return sb.length() == 0 ? "0" : sb.toString();
        }
    }
    

    If we break it into steps, it will have the following steps. 1. compute products from each pair of digits from num1 and num2. 2. carry each element over. 3. output the solution.

    Things to note:

    1. The product of two numbers cannot exceed the sum of the two lengths. (e.g. 99 * 99 cannot be five digit)

    int d1 = num1.charAt(i) - '0';
    int d2 = num2.charAt(j) - '0';
    products[i + j + 1] += d1 * d2;

  • 0
    P

    If the two number are big enough, some specific values of the array products may overflow.


  • 1
    L

    nice solution. Based on this, I developed my own:

    public String multiply(String num1, String num2) {
            if (num1.equals("0") || num2.equals("0")) return "0";
            int n1 = num1.length();
            int n2 = num2.length();
            int[] products = new int[n1 + n2];
            for (int i = n1 - 1; i>= 0; i--) {
                for (int j = n2 - 1; j >= 0; j--) {
                    products[i + j + 1] += ((int)num1.charAt(i) - '0')*((int)num2.charAt(j) - '0');
                }
            }
            int digit = 0;
            StringBuilder sb = new StringBuilder();
            for (int i = n1 + n2 - 1; i >= 0; i--) {
                int tmp = products[i] + digit;
                sb.append(tmp % 10);
                digit = tmp / 10;
            }
            sb.reverse();
            if (sb.charAt(0) == '0') sb.deleteCharAt(0);
            return sb.toString();
    }
    

  • 0
    M

    We can refer to JavaAPI of BigInteger's multiplyToLen function.


  • 4
    K

    Solves for carries along the way instead of having an extra loop to do so.

    public class Solution {
            public String multiply(String num1, String num2) {
                int[] arr = new int[num1.length()+num2.length()];
                for(int i = num1.length()-1; i >= 0; i--) {
                    int carry = 0;
                    for(int j = num2.length()-1; j >= 0; j--) {
                        arr[i+j+1] += carry + (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
                        carry = arr[i+j+1] / 10;
                        arr[i+j+1] %= 10;
                    }
                    arr[i] = carry;
                }
                StringBuilder builder = new StringBuilder();
                int i = 0;
                while(i < arr.length && arr[i] == 0) i++;
                if(i >= arr.length) return "0";
                for(int j = i; j < arr.length; j++) {
                    builder.append(arr[j]);
                }
                return builder.toString();
            }
        }

  • 0
    S

    Can you give an example? Thanks!


  • 0
    Q

    good solution


  • 0
    Y

    @MohnSnow No we can't. The question asks not to do so.


  • 0
    C

    easy to understand.thanks


  • 0
    A

    @lycjava2 how did you come up with this logic? the i+j+1? i did not know how to start wth this solution...


  • 0
    S

    @kevinhsu said in AC solution in Java with explanation:

    arr[i+j+1] += carry + (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
    carry = arr[i+j+1] / 10;
    arr[i+j+1] %= 10;

    Since you run the number loops in reverse order, following code will also work without carry:

    arr[i+j+1] += (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
    arr[i+j] += arr[i+j+1] / 10;
    arr[i+j+1] %= 10;
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.