The editorial says if n>62 directly reject otherwise do brute force in O(n^2) but if have 300 test cases (max possible) each having n around 60. Then we’ll have 300*(62^2) operations which is greater than 10^6.
In this case wouldn’t we get TLE?
But we don’t have 1600 test cases here. If we did have those many test cases then the problem would have been a little bit different. 
This code is very easy than written in the editorial!!
Can anyone help me Pass this code
#include<bits/stdc++.h>
using namespace std;
#define tw() int t; cin>>t; while(t--)
#define ll long long
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define all(x) x.begin(),x.end()
#define allcmp(x) x.begin(),x.end(),cmp
const int MOD = 1000000007;
vl bit(65),bit1,bit2;
void decToBinary(ll n)
{
ll i = 0;
while (n > 0) {
bit[i]+=(n % 2);
n = n / 2;
i++;
}
}
ll decrease1(ll n)
{
ll i = 0;
while (n > 0)
{
bit1[i] += (n % 2) ? -1 : 0;
n = n / 2;
if (bit1[i] == 1)
i++;
}
ll sum = 0;
for (ll i = 0; i < 65; i++)
{
if (bit1[i] > 0)
sum += pow(2, i);
}
return sum;
}
ll decrease2(ll n)
{
ll x = n;
ll i = 0;
while (n > 0)
{
bit2[i] += (n % 2) ? -1 : 0;
n = n / 2;
if (bit2[i] == 1)
i++;
}
ll sum = 0;
for (ll i = 0; i < 65; i++)
{
if (bit2[i] > 0)
sum += pow(2, i);
}
return sum;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
tw(){ bool ok=true;
fill(all(bit), 0);
ll n;
cin >> n;
vl v(n);
ll sum = 0;
map<ll, ll> m;
int z = 0;
for (auto &x : v)
{
cin >> x;
m[x]++;
if (m[x] > 1)
ok = false;
}
for (auto x : v)
{
decToBinary(x);
}
ll sum1 = 0;
for (ll i = 0; i < 65; i++)
{
if (bit[i] > 0)
sum1 += pow(2, i);
}
m[sum1]++;
if (m[sum1] > 1)
ok = false;
bit1 = bit;
bit2 = bit;
for (int i = 0; i < n - 1 && ok; i++)
{
ll x;
if (i > 0)
{
x = decrease1(v[i - 1]);
m[x]++;
if (m[x] > 1)
{
ok = false;
break;
}
}
}
for (int i = n - 1; i > 0 && ok; i--)
{
ll x;
if (i < n - 1)
{
x = decrease2(v[i + 1]);
m[x]++;
if (m[x] > 1)
{
ok = false;
break;
}
}
}
if(ok){cout<<"YES\n";}
else{cout<<"NO\n";}
}
return 0;}It’s nice of you to give an explanation of what went wrong with the test cases. It shows us that we are all humans. It is already hard enough think of alternate solutions that should or shouldn’t pass a problem, let alone preventing them from getting accepted.
3 Likes
i faced the same issue man …i was just keep wondering for a optimised approach.
here everyone has written that around operations upto 10^8 are allowed but here n^2 approach performs 10^10 operations…please someone help me with this issue
Could you prove why? In that case, we’re done right? I know how to continue after this is proved. I just need a solid proof that what I said is true
Did you try reading the editorial? Can you scroll up and read setters’s remarks?
thnx bruuh… it worked but cant understand for which case it could go wrong for my previous submission. I think it should cover all the test cases 
The problem can be done in O(n) as well.
Adding each number has to add 1 or more bits to the OR, otherwise the OR doesn’t change.
Since we can’t add more than ~62 bits, we can’t add more than 62 numbers.
1 Like
simple idea is if we asuume o(a,b) o(c,d) are equal then we acn find some o(0,e)==o(0,f)
so it is equivalent to check o(0,L) ,L from 0 to n-1 are distinct
Plz anyone tell me…Why is the answer always NO after n>=62 ?
- If number of elements is more than 62, Why is the answer NO?
Sure, maximum possible number in the array is 10^18, hence any number has less than or equal to 62 bits in its binary form. But there are 2^62 possible numbers. - Both the solutions of tester and setter are in O(N^2) time complexity. Is there any other solution with lesser time complexity?
If we will bruteforce all possible range as said, then i think the solution will exceed the time limit.
suppose all elements in array are in power of two then it will go to 62 in wrost case [1,2,4,8,16,32,64,128,256,512,…so on ].
How?? I did it in 0(nlogn).I store all array elements in map and Just taking OR of consecutive elements and checking if it is already present or not in map.If it is present then break else add this curr OR value of array to map.
Thanks.
plse share code or try tc
1
3
12 2 7 and see if ans is coming yes or no. If no then correct and if yes then wrong.
Bro, number new generates from OR is non repeated iff when new number contribute towards a differnet bit. So there 62 bits now if ‘n’ is more than that then you will not able to generate a new number because it required one extra bit. I hope you understand.
1 Like