Saturday, July 5, 2014

Multiply Strings

This question should be quite easy. Just divide numbers multiplication into 2 steps: 1) multiplication of one digit and one number, 2) sum up results from step 1.

Time complexity should be O(n^2). I am not sure whether there exits better algorithm. If you know one, please let me know. Thanks.

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) return "0";
        StringBuffer res = new StringBuffer();
       
        String prePrdct = null;
       
        String crntPrdct = null;

        for(int i = num1.length() - 1; i >= 0; i--){
           
            crntPrdct = multiply(num2, num1.charAt(i),num1.length() - 1 - i);
            prePrdct = add(crntPrdct,prePrdct);
        }
       
        return prePrdct;
    }
   
    public String multiply(String num1, char num2,int numZeros){
        StringBuffer res = new StringBuffer();
       
        int get = 0;
       
        for(int i = num1.length() - 1; i >= 0 ; i--){
            int prdct = (num1.charAt(i) - '0') * (num2 - '0') + get;
            get = prdct/10;
            res.append(prdct%10);
        }
       
        if(get != 0) res.append(get);
        res = res.reverse();
        for(int i = 0; i < numZeros;i++){
            res.append(0);
        }
        return res.toString();
    }
   
    public String add(String num1, String num2){
        if(num2 == null) return num1;
        StringBuffer res = new StringBuffer();
       
        if(num1.length() > num2.length()){
            int i = num1.length() - 1;
            int j = num2.length() - 1;
            int get = 0;
            for(; j >= 0; ){
                int sum = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + get;
                get = sum / 10;
                res.insert(0,sum%10);
                i --;
                j --;
            }
           
            for(;i>=0;i--){
                int sum = (num1.charAt(i) - '0') + get;
                get = sum/10;
                res.insert(0,sum%10);
            }
            if(get!=0) res.insert(0,get);
        }
        else{
            int i = num1.length() - 1;
            int j = num2.length() - 1;
            int get = 0;
            for(; i >= 0; ){
                int sum = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + get;
                get = sum / 10;
                res.insert(0,sum%10);
                i --;
                j --;
            }
           
            for(;j>=0;j--){
                int sum = (num2.charAt(j) - '0') + get;
                get = sum/10;
                res.insert(0,sum%10);
            }
            if(get!=0) res.insert(0,get);
        }
       
        return res.toString();
    }
}

No comments:

Post a Comment