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.
n>64?
how can you print no if n>64?? i did not get this part.
Read pigeonhole principle.
ok
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.
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;
mp[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).
Check if your function is nlogn . For more help in this problem you can check the reference https://www.tutorialspoint.com/bitwise-ors-of-subarrays-in-cplusplus
Hope it will solve your problem