package string;

/**
 * Created by gouthamvidyapradhan on 01/02/2018.
 * Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

 Note:

 The length of both num1 and num2 is < 110.
 Both num1 and num2 contains only digits 0-9.
 Both num1 and num2 does not contain any leading zero.
 You must not use any built-in BigInteger library or convert the inputs to integer directly.

 Solution: O(N x M) where N and M are length of strings
 */
public class MultiplyStrings {

    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        System.out.println(new MultiplyStrings().multiply("00", "0000"));
    }

    public String multiply(String num1, String num2) {
        if((num1.length() == 1 && num1.equals("0")) ||  (num2.length() == 1 && num2.equals("0"))) return "0";
        if(num1.length() < num2.length()) return multiply(num2, num1);
        String temp2 = "", trail = "";
        int carry = 0;
        for(int i = 0; i < num1.length(); i ++){
            temp2 += "0";
        }
        for(int i = num1.length() - 1; i >= 0; i --){
            String temp1 = "";
            for(int j = num2.length() - 1; j >= 0; j --){
                int prod = Integer.parseInt(String.valueOf(num2.charAt(j))) *
                        Integer.parseInt(String.valueOf(num1.charAt(i)));
                prod += carry;
                temp1 = (prod % 10) + temp1;
                carry = (prod / 10);
            }
            if(carry > 0){
                temp1 = String.valueOf(carry) + temp1;
                carry = 0;
            }
            String temp3 = add(temp1, temp2);
            temp2 = temp3.substring(0, temp3.length() - 1);
            trail = temp3.substring(temp3.length() - 1, temp3.length()) + trail;
        }
        return temp2 + trail;
    }

    private String add(String s1, String s2){
        String result = "";
        int carry = 0;
        int i = s1.length() - 1, j = s2.length() - 1;
        for(; i >= 0 || j >= 0; i --, j--){
            int l = (i >= 0) ? Integer.parseInt(String.valueOf(s1.charAt(i))) : 0;
            int r = (j >= 0) ? Integer.parseInt(String.valueOf(s2.charAt(j))) : 0;
            int sum = l + r + carry;
            carry = sum / 10;
            result = sum % 10 + result;
        }
        if(carry > 0){
            result = carry + result;
        }
        return result;
    }

}