In this HackerEarth Mattey Multiplication problem solution, Mattey has an assignment that he should submit tomorrow. The assignment has one question which asks to write a program to multiply two numbers without using the ''* operator. As Mattey finds no interest in this subject, he never listens to classes and so does not know about shift operators.

He comes to you to learn about this topic. You can explain in any manner you wish. But for this question, given N and M, write an equation using left shift operators whose result will be equal to the product N * M.


HackerEarth Mattey Multiplication problem solution


HackerEarth Mattey Multiplication problem solution.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    assert(t >= 1 && t <= 50000);
    while(t--)
    {
        long long int n,m;
        scanf("%lld %lld",&n,&m);
        assert(n >= 1 && n <= 10000000000000000);
        assert(m >= 1 && m <= 10000000000000000);
        int a[100] = {0};
        int len = 0;
        int l1 = -1;
        while(m > 0)
        {
            a[len] = m%2;
            if(a[len] == 1 && l1 == -1)
                l1 = len;
            m/=2;
            len++;
        }/*
        for (int i = 0; i < len; ++i)
        {
            printf("%d", a[i]);
        }
        printf("\n");*/
        for (int i = len-1; i > l1; --i)
        {
            if(a[i] == 1)
                printf("(%lld<<%d) + ", n,i);
        }
        printf("(%lld<<%d)\n", n,l1);
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;
const int mod=1000000007;

#define SSTR( x ) dynamic_cast< ostringstream & >( \
                ( ostringstream() << dec << x ) ).str()
#define fill(a,b) memset(a,b,sizeof(a))
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define f first
#define s second
#define Pi 3.1415926535897
#define checkbit(n,b) ( (n >> b) & 1)
#define bsearch(arr,ind) (int)(lower_bound(all(arr),ind)-arr.begin())
#define LL long long int
#define eps 1e-9
#define all(x) (x).begin(),(x).end()
LL C(int n,int k){long long ans=1;k=k>n-k?n-k:k;int j=1;for(;j<=k;j++,n--){if(n%j==0){ans*=n/j;}else if(ans%j==0){ans=ans/j*n;}else{ ans=(ans*n)/j;}} return ans;}
LL powmod(LL a,LL b) {LL res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
LL gcd(LL a,LL b){if(a==0)return(b);else return(gcd(b%a,a));}
LL powmod(LL a,LL b,LL m) {LL res=1;a%=m;for(;b;b>>=1){if(b&1)res=res*a%m;a=a*a%m;}return res;}
int countSetBits(LL n){unsigned int count = 0;while(n){n &= (n-1) ;count++;}return count;}
int main(){
    int t;
    scanf("%d",&t);
    assert(t>0 and t<=pow(10,5));
    while(t--){
        LL n,m;
        scanf("%lld %lld",&n,&m);
        assert(n>0 and n<pow(10,16));
        assert(m>0 and m<pow(10,16));
        int count=0;
        int j=0;
        vector <int> s(100);
        while(m){
            if(m%2){
                s[j]=count;
                j++;
            }
            m/=2;
            count+=1;
        }
        for(int i=j-1;i>=0;i--){
            if(i==0){
                printf("(%lld<<%d)\n",n,s[i]);
            }
            else{
            printf("(%lld<<%d) + ",n,s[i]);
            }
        
        }
        
    }
    return 0;
}