Description

LeetCode 43

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.

Analysis

I think this problem is the base of implementing big integer class. The basic idea should be mastered.

Draw the graph of the multiplying process then we can obtain a conclusion, the length of result is at most the sum of the length of num1 and num2. And \(num1[i]*num2[j]\) will be placed at indices \([i+j, i+j+1]\). Then just accumulate the elements placed every time.

Solution

class Solution {
    public String multiply(String num1, String num2) {
        String r="";
        int[] res=new int[num1.length()+num2.length()];
        int s,mul;
        for(int i=num1.length()-1;i>=0;i--)
        {
            for(int j=num2.length()-1;j>=0;j--)
            {
                s=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                s=s+res[i+j+1];
                res[i+j]=res[i+j]+s/10;
                res[i+j+1]=s%10;
            }

        }
        for(int i=0;i<res.length;i++)
        {
            if(!(r.length()==0&&res[i]==0)) r=r+res[i];//Delete "0"s at high digits
        }
        if(r.length()==0) return "0";
        else return r;
    }
}

Reference

[1] https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation

Leave a Reply

Your email address will not be published. Required fields are marked *