How to get rid of "Time Limit Exceeded"

Question

I try to solve some problems in a online website. And I've a solved a problem with simple C++ it worked well but it sometime throw a "Time limit exceeded" error. How to get rid of this?

Here is the question that I solved

There are two integers A and B. You are required to compute the bitwise AND amongst all natural numbers lying between A and B, both inclusive.

Here is my code.

 #include<iostream>
using namespace std;
int main()
{
    int t,a,b;
    long ans;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        ans=a;
        for(int i=a+1; i<=b; i++)
        {
            ans=ans&i;
        }
        cout<<ans<<endl;
    }
}

Answer 1

If you have two numbers, X and Y, they are represented by a finite sets of bits:

X = Bx(1), ..., Bx(n)

and

Y = By(1), ..., By(n)

The bitwise AND between the two can be computed as

X ^ Y = (Bx(1) ^ By(1)), ..., (Bx(n) ^ By(n))

A B A ^ B

0 0 0

0 1 0

1 0 0

1 1 1

We observe that:

• all the bits can be computed separately, we have as many equations as many bits
• in a sequence of logical statements, where AND is the operator, the result is 0 if and only if ANY of the items is 0

So, if any numbers are pair, then the last bit is 0. Otherwise, the last bit will be 1. If any number will have a 0 as the penultimate bit, then the result for that bit will be 0. Otherwise it will be 1.

As a general rule, based on the pigeonhole principle, proposed by Dirichlet, if you have enough consecutive (elements) for a given bit, then the result for that bit will be 0. For example, for the very last bit you have two variations, therefore, if you have at least two numbers in your consecutive set, then the last bit will be 0. If we take the very next bit, then you have four variations: 00, 01, 10 and 11. So, if you have at least 3 numbers in your consecutive set, then this bit is 0. For the next bit, you have 8 variations: 000, 001, 010, 011, 100, 101, 110, 111. So, if you have at least 5 numbers in your consecutive set, then this bit is 0.

Now, since we have a simple rule that determines most bits if there are many items, you will end up with a few bits that exceed in their number of variations the rule I have described above. For those bits you can check the first and the last number. If they have the same value for that bit, then that value will be the result, be it 0 or 1.