Is there any much easier method?


  • 0
    J

    The codes I wrote is as follows, which has been accepted , but obviously it is very rough and long, I wonder if there is any easier method?

    Given two numbers represented as strings, return multiplication of the numbers as a string.

    Note: The numbers can be arbitrarily large and are non-negative.

    public class Solution {
    
      public String multiply(String num1, String num2) {
            if(num1.equals("0") || num2.equals("0")){
                return "0";
            }
            
            if(num1.length() < num2.length()){
                String temp = num1;
                num1 = num2;
                num2 = temp;
            }
    
            ArrayList<ArrayList<String>> rowsList = new ArrayList<ArrayList<String>>();
    
            int num1Len = num1.length();
            int num2Len = num2.length();
    
            boolean firstRow = true;
            int totalDigits = 0;
            for (int i = 0; i <= num2Len - 1; i++) {
                int num2Elem = Integer.valueOf(String.valueOf(num2.charAt(i)));
    
                ArrayList<String> rowList = new ArrayList<String>();
                int carryVal = 0;
                for (int j = num1Len - 1; j >= 0; j--) {
                    int num1Elem = Integer.valueOf(String.valueOf(num1.charAt(j)));
                    int product = num1Elem * num2Elem + carryVal;
                    String productStr = String.valueOf(product);
                    if (productStr.length() == 1) {
                        rowList.add(0, productStr);
                        carryVal = 0;
                    } else if (productStr.length() == 2) {
                        rowList.add(0, String.valueOf(productStr.charAt(1)));
                        carryVal = Integer.valueOf(String.valueOf(productStr
                                .charAt(0)));
                    }
                }
                if(carryVal != 0){
                    rowList.add(0, String.valueOf(carryVal));
                }
    
                // add zero digits
                int zeroDigits = num2Len - 1 - i;
                if (zeroDigits > 0) {
                    for (int k = 1; k <= zeroDigits; k++) {
                        rowList.add("0");
                    }
                }
    
                if (firstRow) {
                    totalDigits = rowList.size();
                    firstRow = false;
                } else {
                    int originalSize = rowList.size();
                    for (int m = 1; m <= totalDigits - originalSize; m++) {
                        rowList.add(0, "0");
                    }
                }
    
                rowsList.add(rowList);
    
            }
    
            // add the rows
            ArrayList<String> resultList = new ArrayList<String>();
            int carryVal = 0;
            for (int digitIndex = totalDigits - 1; digitIndex >= 0; digitIndex--) {
                int digitVal = 0;
                for (int i = 0; i < rowsList.size(); i++) {
                    ArrayList<String> row = rowsList.get(i);
                    digitVal += Integer.valueOf(row.get(digitIndex));
                }
                digitVal += carryVal;
                String digitStr = String.valueOf(digitVal);
                if (digitStr.length() == 1) {
                    resultList.add(0, digitStr);
                    carryVal = 0;
                } else {
                    resultList.add(0,
                            String.valueOf(digitStr.charAt(digitStr.length() - 1)));
                    carryVal = Integer.valueOf(digitStr.substring(0,
                            digitStr.length() - 1));
                }
            }
            if(carryVal != 0){
                resultList.add(0, String.valueOf(carryVal));
            }
    
            StringBuilder sb = new StringBuilder();
            for (String elem : resultList) {
                sb.append(elem);
            }
            return sb.toString();
        }
    
    }

  • 1
    S

    My method takes O(n+m) space and O(nm) time. The idea is to multiply each digit from num2 (vice versa if take num1) to num1. The product is saved as another string, then it is left shifted accordingly and added to the output. The codes is a bit long but structure is simple indeed.

    class Solution {
    public:
    // each digit of num2 needs to multiply with num1
    // keep adding each such product to the output
    // note: all intermediate results are saved as strings
    
        string multiply(string num1, string num2) {
            if (num1 == "0" || num2 == "0")
                return "0";
                
            string res;
            string str;
            for (int i = num2.size()-1; i >= 0; i--) {
                // get a product of num1*num2[i]
                str = digitTimesNum (num1, num2[i]);
                str.append(num2.size()-i-1, '0');
                res = sumNumbers (res, str);
            }
            return res;
        }
        
        // get a product of a num and a digit
        string digitTimesNum (const string & num, const char d) {
            string res;
            if (d == '0')
                return "0";
                
            char carry_on = '0';
            for (int i = num.size()-1; i >= 0; i--) {
                int p = (num[i]-'0') * (d - '0') + (carry_on - '0');
                char newd = char ('0' + p%10);
                carry_on = char ('0' + p/10);
                res.insert(res.begin(), newd);
            }
            if (carry_on - '0' > 0)
                res.insert(res.begin(), carry_on);
            
            return res;
        }
        
        // get a sum of two numbers
        string sumNumbers (string & num1, string & num2) {
            string res;
            if (num1.size() == 0) {
                res = num2;
                return res;
            }
            
            // fill 0 to the shorter num so two numbers have same length
            int n1 = num1.size();
            int n2 = num2.size();
            if (n1 < n2) num1.insert(num1.begin(), n2-n1, '0');
            if (n2 < n1) num2.insert(num2.begin(), n1-n2, '0');    
            int n = max(n1, n2);
            char carry_on = '0';
            for (int i = n-1; i >= 0; i--) {
                int p = (num1[i]-'0') + (num2[i]-'0') + (carry_on - '0');
                char newd = char ('0' + p%10);
                carry_on = char ('0' + p/10);
                res.insert(res.begin(), newd);
            }
            if (carry_on - '0' > 0)
                res.insert(res.begin(), carry_on);
                
            return res;
        }
    };

  • 1
    N

    Another Java method that takes O(n+m) in space as it save the result in an array n+m size (where n and m are strings lengths) and O(n*m) time to complete. I managed it looping the strings from the end, saving both carries (one for multiplications and another for sums) and storing the result in the array depending on the position of the numbers i was multiplying.

    public String multiply(String num1, String num2) {
        
        if ((num1.equals("")) ||
            (num2.equals("")) ||
            (!num1.matches("[0-9]+")) ||
            (!num2.matches("[0-9]+")))
            return "";
            
        int []output = new int[num1.length() + num2.length()];
        
        for (int i=num1.length()-1 ; i >= 0 ; i--) {
            int carryM = 0;
            int carryS = 0;
            
            for (int j=num2.length()-1 ; j >= 0 ; j--) {
                
                int m1 = Integer.parseInt(num1.substring(i, i+1));
                int m2 = Integer.parseInt(num2.substring(j, j+1));
                int mult = (m1 * m2) + carryM;
                carryM = mult / 10;
                int rest = mult % 10;
                
                int inc = output[j+i+1] + rest + carryS;
                output[j+i+1] = inc % 10;
                carryS = inc / 10;
            }
            output[i] = carryM + carryS;
        }
        
        StringBuilder out = new StringBuilder();
    
        boolean firstZeros = true;
        for (int i=0 ; i < output.length ; i++) {
            if ((output[i] == 0) && (i != output.length-1)) {
                if (!firstZeros)
                    out.append(output[i]);
            } else {
                out.append(output[i]);
                firstZeros = false;
            }
        }
    
        return out.toString();
    }

  • 0
    V

    A very simple solution in C++. Time: 24ms
    My Idea is to calculate the digits of the answer 1 by one. To calculate each digit of ans, all we need to know is previous carry and sum of product of all pair of digits whose multiplication can affect this digit of answer. eg unit digit of answer can be calculated by simply multiplying the unit digits of each number. similarly tens digit of answer can be calculated by carry of units place and sum of product of (tens digit of 1st number with unit digit of second) and ( unit digit of first num with tens digit of second) and so on...
    after that add carry to answer and remove leading zeroes.

    PS: I have stored answer in reverse order, so after calculating the value of answer i have reversed it to get back original product of numbers. this helps in increased speed.

    class Solution {
    public:
    string multiply(string a, string b) {
        string ans = "";
        int x,y, c = 0; // carry
        for (int i = 0; i < a.size() + b.size() - 1; i++) {
            x = (int)b.size();
            y = (int)a.size() - 2 - i;
            while (--x >= 0) {
                if (++y < a.size()) 
                    c = c + ((int)b[x] - '0')*((int)a[y] - '0');
            }
            ans += (char)(c % 10 + '0');
            c = c / 10;
        }
        while (c) {
            ans += (char)(c % 10 + '0');
            c = c / 10;
        }
        reverse(ans.begin(), ans.end());
        while (ans[0] == '0' && ans.size() > 1) ans.erase(0, 1);
        return ans;
    }
    };

  • 5
    M

    Here's my C++ implementation.

    Very simple indeed.

    1. Create a int vector for storing the final result.

    2. Calculate the value of each digit combination, add up the value to the corresponding position in the vector. Carry if current position is lager than 10.

    3. Output the value from high to low.

        string multiply(string num1, string num2) {
    
        const char *p1 = num1.c_str();
        const char *p2 = num2.c_str();
    
        vector<unsigned int> fin(num1.length() + num2.length());
    
        for (int i = 0; i < fin.size(); ++i) {
            fin[i] = 0;
        }
    
        int a;
        int b;
        int pos = 0;
    
        unsigned int end1 = num1.length() - 1;
        unsigned int end2 = num2.length() - 1;
    
        string result = "0";
    
        for (unsigned int i = 0; i <= end1; ++i) {
    
            a = p1[end1 - i] - '0';
    
            for (unsigned int j = 0; j <= end2; ++j) {
    
                pos = i+j;
                b = p2[end2 - j] - '0';
    
                fin[pos] += a * b;
    
                // carry
                if (fin[pos] >= 10) {
                    fin[pos + 1] += fin[pos] / 10;
                    fin[pos] = fin[pos]  % 10;
                }
            }
        }
    
        bool start = false;
    
        for (int i = fin.size() - 1 ; i >= 0; --i) {
    
            if (!start) {
                if (fin[i] != 0) {
                    start = true;
                    result = (char)('0' + fin[i]);
                }
            }
            else {
                result = result + (char)('0' + fin[i]);
            }
        }
    
        return result;
    }

  • 0
    R

    Check my answer. I think the key is to decouple several steps.

    public class MultiplyStrings {
    	int[] calc;	
    	int length;
        public String multiply(String num1, String num2) {
        	//Initial Check
        	if (num1==null||num2==null||num1.length()==0||num2.length()==0)
        		return null;
        	//Setup
        	length=num1.length()+num2.length();
            calc=new int[length];
            Arrays.fill(calc, 0);
            //Do the work
            for (int i=num1.length()-1;i>=0;i--)
            	for (int j=num2.length()-1;j>=0;j--)
            		addChar(multiplyChar(num1.charAt(i),num2.charAt(j)),length-2-i-j);
            //Data marshalling
            char[] results = new char[length];
            for (int i=0;i<length;i++)
            	results[i]=(char) (calc[i]+'0');
            //Find the first Non-zero
            int i=0;
            while (results[i]=='0'&&i<length-1) i++;
            
            return new String(results,i,length-i);
        }
        private int multiplyChar(char num1,char num2){
        	int n1=num1-'0',n2=num2-'0';
        	int sum=n1*n2;    		
        	return sum;  
        	
        }
        private void addChar(int sum,int shift){
    
        	int i=length-1-shift;
        	while(sum>0){
        		sum+=calc[i];
        		calc[i--]=sum%10;
        		sum/=10;
        	}    	
        }
    }

  • 0
    F

    good idea to use vector<int> to store the result, saves a lot of code to deal with carry


  • 0
    P
    string multiply(string num1, string num2) {
        string res;
        int carry = 0;
        
        for (int i1 = num1.size() - 1;i1 >= 0; i1--)
        {
            int reversePos = num1.size() + num2.size() - 2 - i1;
            for (int i2 = num2.size() - 1; i2 >= 0; i2--)
            {
                int num = (num1[i1] - '0') * (num2[i2] - '0') + carry + get(res, reversePos - i2);
                carry = num / 10;
                set(res, reversePos - i2, num % 10);
            }
            set(res, ++reversePos, carry % 10);
            carry /= 10;
        }
        reverse(res.begin(), res.end());
        while (res[0] == '0' && res.size() > 1)   res.erase(0,1);
        return res;
    }
    
    int get(string & s, int i)
    {
        return s.size() > i ? s[i] - '0' : 0;
    }
    
    void set(string & s, int i, int num)
    {
        if (s.size() > i)
            s[i] = num + '0';
        else
            s += (num + '0');
    }
    

    I think my answer is clear, it saves reserved answer, and at the end , flip the answer and delete preceding 0s.


  • 7
    K

    here is my solution, just calculate each digit of the answer using sum and carry.
    time is O(n*m), space is O(n+m)

    class Solution {
    public:
        string multiply(string num1, string num2) {
            string result;
            int carry = 0;
            if(num1.size()==1&&num1[0]=='0'||num2.size()==1&&num2[0]=='0')
                return "0";
            for(int i = 1 ; i < num1.size()+num2.size(); ++i){
                int sum = carry;
                for(int j = 1 ; j <= num1.size(); ++j){
                    if(i+1-j>=1&&i+1-j<=num2.size())
                        sum += (num1[num1.size()-j]-'0')*(num2[num2.size()-1-i+j]-'0');
                }
                carry = sum/10;
                result.insert(result.begin(),sum%10+'0');
            }
            if(carry>0) result.insert(result.begin(),carry+'0');
            return result;
        }
    }; 

  • 0
    K
    This post is deleted!

  • 0
    K
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    Y

    My accepted code using long multiplicity:

     public String multiply(String num1, String num2) {
            if(num1.equals("0")||num2.equals("0")) return "0";
            String r="";
            int s=0;
            int m=num1.length();
            int n=num2.length();
          for(int i=0;i<m+n-1;i++){
              int p=0;
              for(int j=0;j<Math.min(m,i+1);j++){
                  if(i-j<n)
                  p=p+(num1.charAt(m-1-j)-48)*(num2.charAt(n-1-(i-j))-48);
              }
              p=p+s;
              r=String.valueOf((p%10))+r;
              s=p/10;
          }
          if(s==0) return r;
          return String.valueOf(s)+r;
        }

Log in to reply
 

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