Thursday, December 6, 2018

Multiply two integers represented by strings

Multiply two integers represented by strings: 

This is basic multiplication technique which we used to learn in our elementary schools.

Steps:
1. Length of Result of multiplication is max of sum of the length of two strings (prefixes as zeros)
2. Formula : sum = num1[i] * num2[j] + result[I_n1+i_n2] + carry : 3*9+currvalue+carry
3. where carry = sum/10 (quotient) and result = sum%10 (remainder) ,
 if sum =17 then carry =1 and result=7
4. Add all carry after 1 iteration to result i.e. result +=carry; if carry>0
5. Remove all zeros prefixes
6. Form string from backward of result




public class Solution {
    public string Multiply(string num1, string num2) {
       int i_n1 = 0; 
       int i_n2 = 0;
        int[] result = new int[num1.Length+num2.Length];
       
        for(int i=num1.Length-1;i>=0;i--)
        {
            int carry=0;
            int n1 = num1[i] -'0';
            i_n2=0;
            for(int j=num2.Length-1;j>=0;j--)
            {
                int n2 = num2[j] - '0';
                int sum = n1*n2 + result[i_n1+i_n2] + carry;
                carry = sum/10;
                result[i_n1+i_n2] = sum % 10;
                i_n2++;                  
            }
           
            if (carry > 0)
            result[i_n1 + i_n2] += carry;
            i_n1++;
           
        }
       
        int  k = result.Length - 1;
        while (k>=0 && result[k] == 0)
           k--;
       
        if (k == -1)
          return "0";
       
        string s = string.Empty;
       
        while(k>=0)
            s += result[k--].ToString();
        return s;
 
    }
}








No comments:

Post a Comment