RANGE AND - RGAND CodeChef Easy-Medium Question

Welcome back !

Understanding the question is pretty simple .

We just need to find the sum .

Doing iteratively is simple but it would exceed time limit .

So , we figure out a better solution , lets discuss the strategy .

So , if l is equal to r , it is theanswer , else we take l an find its lsb.

Any bit which is 0 in l will never count to the answer .

So , we take the first bit which is 1 in l and find the number of times it will contribute to the answer and so on .

the number of times it will contribute will be till the first time it becomes 0 or we reach r and we continuously repeat the process .

Hence , we take modulus at each point to keep things in range .

Please take a look at the following code for better understanding :-

Code :-

#include <iostream>

#include<algorithm>

#include <bits/stdc++.h>

using namespace std;

int main() {

    unsigned long long int mod=1000000007;

    long int t;

    cin>>t;

    while(t--)

    {

        unsigned long long int l,r;

        cin>>l>>r;

        unsigned long long int ans=0;

        if(l==r)

        {

            cout<<l<<endl;

        }

        else

        {

            unsigned long long int i=0,a;

            while(i!=63)

            {

                if(l&(1LL<<i))

                {

                    unsigned long long int k=(1LL<<i) - (l&((1LL<<i) -1));

                    if(k<(r-l+1))

                    {

                        a=k;

                    }

                    else

                    {

                        a=r-l+1;

                    }

                    ans=(ans+(((1LL<<i)%mod)*(a%mod))%mod)%mod;

                }

                //cout<<ans<<" ";

                i++;

            }

            cout<<ans<<endl;

        }

    }

return 0;

}

Please leave your doubts and queries in comments section .