Karatsuba Algorithm

 Given two binary strings that represent value of two integers, find the product of two strings. For example, if the first bit string is “1100” and second bit string is “1010”, output should be 120.

Input:
First line consists of T test cases. Only line of every test case consists of 2 binary strings.

Output:
Single line output, print the multiplied value.

Constraints:
1<=T<=100
1<=Length of string<=100

Example:
Input:
2
1100 01
01 01
Output:
12
1

The link of this problem is https://practice.geeksforgeeks.org/problems/karatsuba-algorithm/0

Solution(CPP):

#include<iostream>

using namespace std;

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        string a;

        string b;

        cin>>a>>b;

        stack<int> s1;

        stack<int> s2;

        for(int i=0;i<a.length();i++)

        {

            s1.push(a[i]-'0');

        }

        for(int i=0;i<b.length();i++)

        {

            s2.push(b[i]-'0');

        }

        int k1=0,sum1=0;

       //Converting from binary to decimal

        while(!s1.empty())

        {

            sum1=sum1+s1.top()*pow(2,k1);

            k1++;

            s1.pop();

        }

        int k2=0,sum2=0;

        while(!s2.empty())

        {

            sum2=sum2+s2.top()*pow(2,k2);

            k2++;

            s2.pop();

        }

        cout<<sum1*sum2<<endl;

    }

return 0;

}