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();
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