You can directly print “NO” if n > 64. Also, using unorderd_map is not O(1). As n gets large, there can be collisions and unordered_map access can become O(n) which might have cause TLE.


how can you print no if n>64?? i did not get this part.

Read pigeonhole principle.

1 Like

what if we use map?

After n > 64 we can definitely guarantee that there will be repetitions. As @akshay_1 said, we can say this using pegionhole principle. The editorials has more information, take a look.

1 Like

Your check function is n\text{ log }n and you’re calling it n times. So the overall complexity is n^2 \text{ log }n, which results in TLE.

Till Now , I had not written many recursive codes but as per my understanding I can say that in line 20 you are using recursion in for loop which will make time complexity of the loop O(n^2) approximately and when combined with loop of main it becomes O(n^3) with constant being on their places

there are around 60 bits for the number 2^18.

In the worst case take powers of two which always occupy a single bit.

from 2^0 upto 2^60 eveyone will have a unique bit in atleast one position.

but after that no matter what you will always have a number which whose bit will overlap with one of these numbers and thus leaving us with a pair which won’t have distinct OR.

you can call it pigeonhole.

thanks very much

but sir here is one solution whose worst acse complexuty apppears to be O(n^3) but despite of that code is accepted.
for (ll i = 0; i < n; i++)
for(ll j=i;j<n;j++)
ll temp=0;
for (ll k=i;k<=j;k++)
temp= (temp | a[k]);
//cout<<"***Temp = "<<temp<<endl;
//cout<<"TEMP= “<<temp;
//cout<<” mp[temp]= "<<mp[temp]<<endl;

That is because of weak test cases. Also whenever you post a piece of code, format it.

And I was wrong about the complexity. As @dhruv788 has mentioned, you’re function is O(n^2), and you’re calling it n times. So the overall complexity is O(n^3). On top of that, if we add collisions in your map, it might go up to O(n^4).

1 Like

Check if your function is nlogn . For more help in this problem you can check the reference
Hope it will solve your problem