Thursday, March 6, 2014

Leetcode: Multiply Strings

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.

Solution:

We precalculate num1 multiplied by [0...9] and keep the result afterwards we just follow the algorithm typical of multiplying in paper, i.e. 123*456 = 123*6+ 123*5 *10 + 123*4*100, where the last multiplication is just adding zeros.
public class Solution {
    public String multiply(String num1, String num2) 
    {
        StringBuilder result=new StringBuilder();
        int carryOn=0;
        for(int i=num2.length()-1; i>=0; i--)
        {
              StringBuilder tempResult=new StringBuilder();
              for(int j=num1.length()-1; j>=0; j--)
              {
                carryOn += (Character.getNumericValue(num1.charAt(j)) * Character.getNumericValue(num2.charAt(i)));
                tempResult.insert(0,carryOn%10);
                carryOn /= 10;
              }
              if(carryOn>0)
              {
                tempResult.insert(0,carryOn%10);
                carryOn =0;
              }
              for(int j=i; j<num2.length()-1; j++)
                tempResult.append('0');
              result = sum(result,tempResult);
        }
        removeZeros(result);
        return result.toString();
    }
    
    public StringBuilder sum(StringBuilder sum1, StringBuilder sum2)
    {
        int carryOn = 0;
        StringBuilder result = new StringBuilder();
        for(int i=0; i<sum2.length() || i<sum1.length(); i++)
        {
            if(i<sum2.length())
                carryOn += Character.getNumericValue(sum2.charAt(sum2.length()-1-i));
            if(i<sum1.length())
                carryOn += Character.getNumericValue(sum1.charAt(sum1.length()-1-i));
            result.insert(0,carryOn%10);
            carryOn /= 10;
        }
        if(carryOn>0)
                result.insert(0,carryOn%10);
        return result;
    }
    
    public void removeZeros(StringBuilder num)
    {
        while(num.length()>1 &&num.charAt(0)=='0')
            num.deleteCharAt(0);
    }
}

No comments :

Post a Comment