Saturday, December 17, 2016

multiply 2 strings in c++

Given two numbers as stings s1 and s2 your task is to multiply them. You are required to complete the function multiplyStrings which takes two strings s1 and s2 as its only argument and returns their product as strings.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow . Each test case contains two strings s1 and s2 .

Output:
For each test case in a new line the output will be a string denoting the product of the two strings s1 and s2.

Constraints:
1<=T<=100
1<=length of s1 and s2 <=100

Example(To be used only for expected output) :
Input:

2
33 2
11 23
Output:
66
253

http://www.practice.geeksforgeeks.org/problem-page.php?pid=700383

string multiplyCharStr(char r, string s2) {
    int j = r - '0';
    int carry = 0;
    int val = 0;
    int len = s2.length();
    string ret;
    char cr;
    for (int i = len-1; i>=0; i--) {
        val = j*(s2[i]-'0');
        cr = '0' + (val + carry)%10;
        ret = (cr) + ret;
        if (val + carry >= 10)
            carry = (val+carry)/10;
        else
        carry = 0;
    }
    if (carry > 0)
    ret = ((char)('0' + carry)) + ret;
    return ret;
}

string addstring(string s1, string s2)
{
int len1 = s1.length() -1, len2 = s2.length() -1, carry = 0, val=0, j=0;
string s3;
while (len1 >= 0 && len2 >= 0) {
val = s1[len1] - '0' + s2[len2] - '0' + carry;
s3 = (char)(val%10 + '0') + s3;
len1--;
len2--;
carry = val/10;
}
while (len1 >= 0) {
val = s1[len1] - '0' + carry;
s3 = (char)(val%10 +'0') + s3;
len1--;
carry = val/10;
}
while (len2 >= 0) {
val = s2[len2] - '0' + carry;
s3 = (char)(val%10 +'0') + s3;
len2--;
carry = val/10;
}
if (carry>0)
s3 = (char)(carry +'0') + s3;
while (s3[j] == '0')
j++;
if (j>0 || s3[j] == '0')
s3.erase(0, j);
return s3;
}

string multiplyStrings(string s1, string s2) {
   //Your code here
   string s3,s4;
   int len1 = s1.length(), len2 = s2.length();
   if (len1>len2) {
    string temp = s1;
    int temi = len1;
    len1 = len2;
    s1=s2;
    s2=temp;
    len2 = temi;
   }
   
   s3 = multiplyCharStr(s1[len1-1], s2);
   if (len1 == 1) return s3;
   s4 = multiplyCharStr(s1[len1-2], s2);
 
   s4 = s4 + '0';
 
   s3 = addstring(s3,s4);
   if (len1 == 2) return s3;
   for (int i = len1-3; i>=0;i--) {
    s4 = multiplyCharStr(s1[i], s2);
    for (int j= 0; j < len1 - i - 1; j++)
    s4 = s4 + '0';
    s3 = addstring(s3,s4);
   }
   return s3;
}

No comments:

Post a Comment