I’ve seen such solutions too.
Yes please 
The idea behind this logic is simple …If two substring have same OR value then OR value from the start(or may be end) will become steady at second substring .
1 Like
Can someone please look into my code and explain where i was going wrong.
The method was: first i have built a prefix matrix whose i,j th element stores among elements in the range [0,…,j] total number of elements whose i th bit is set.
Then i have considered all possible ranges [1 <= l <=r <=n] and using the prefix matrix found out which of the 64 bits should be set in the answer for that particular range (the OR of all elements in the given range).
Like this OR values of all ranges are obtained. Then i just check if all of them are unique or not.
My approach is different from the one mentioned.
I first sorted the array in descending order and then traversed from left to right. I maintained a variable X that stored the OR of all the number seen till now. At each step I ORed X with the current index value and checked if the value of X has changed or not.
If it didn’t then I broke the loop and printed “NO”.
I got AC. Can anybody confirm if the approach was actually correct. Thanks.
Think in terms of binary - what is the largest power of 2 which is less than 1018 it is 259
Now what it means , how many different values we can take of power of 2 which is 59 -
see-
1 000000000000000000000000000000000000000000000000000000000001
2 000000000000000000000000000000000000000000000000000000000010
4 000000000000000000000000000000000000000000000000000000000100
8 000000000000000000000000000000000000000000000000000000001000
16 000000000000000000000000000000000000000000000000000000010000
32 000000000000000000000000000000000000000000000000000000100000
64 000000000000000000000000000000000000000000000000000001000000
128 000000000000000000000000000000000000000000000000000010000000
256 000000000000000000000000000000000000000000000000000100000000
512 000000000000000000000000000000000000000000000000001000000000
1024 000000000000000000000000000000000000000000000000010000000000
2048 000000000000000000000000000000000000000000000000100000000000
4096 000000000000000000000000000000000000000000000001000000000000
8192 000000000000000000000000000000000000000000000010000000000000
16384 000000000000000000000000000000000000000000000100000000000000
32768 000000000000000000000000000000000000000000001000000000000000
65536 000000000000000000000000000000000000000000010000000000000000
131072 000000000000000000000000000000000000000000100000000000000000
262144 000000000000000000000000000000000000000001000000000000000000
524288 000000000000000000000000000000000000000010000000000000000000
1048576 000000000000000000000000000000000000000100000000000000000000
2097152 000000000000000000000000000000000000001000000000000000000000
4194304 000000000000000000000000000000000000010000000000000000000000
8388608 000000000000000000000000000000000000100000000000000000000000
16777216 000000000000000000000000000000000001000000000000000000000000
33554432 000000000000000000000000000000000010000000000000000000000000
67108864 000000000000000000000000000000000100000000000000000000000000
134217728 000000000000000000000000000000001000000000000000000000000000
268435456 000000000000000000000000000000010000000000000000000000000000
536870912 000000000000000000000000000000100000000000000000000000000000
1073741824 000000000000000000000000000001000000000000000000000000000000
2147483648 000000000000000000000000000010000000000000000000000000000000
4294967296 000000000000000000000000000100000000000000000000000000000000
8589934592 000000000000000000000000001000000000000000000000000000000000
17179869184 000000000000000000000000010000000000000000000000000000000000
34359738368 000000000000000000000000100000000000000000000000000000000000
68719476736 000000000000000000000001000000000000000000000000000000000000
137438953472 000000000000000000000010000000000000000000000000000000000000
274877906944 000000000000000000000100000000000000000000000000000000000000
549755813888 000000000000000000001000000000000000000000000000000000000000
1099511627776 000000000000000000010000000000000000000000000000000000000000
2199023255552 000000000000000000100000000000000000000000000000000000000000
4398046511104 000000000000000001000000000000000000000000000000000000000000
8796093022208 000000000000000010000000000000000000000000000000000000000000
17592186044416 000000000000000100000000000000000000000000000000000000000000
35184372088832 000000000000001000000000000000000000000000000000000000000000
70368744177664 000000000000010000000000000000000000000000000000000000000000
140737488355328 000000000000100000000000000000000000000000000000000000000000
281474976710656 000000000001000000000000000000000000000000000000000000000000
562949953421312 000000000010000000000000000000000000000000000000000000000000
1125899906842624 000000000100000000000000000000000000000000000000000000000000
2251799813685248 000000001000000000000000000000000000000000000000000000000000
4503599627370496 000000010000000000000000000000000000000000000000000000000000
9007199254740992 000000100000000000000000000000000000000000000000000000000000
18014398509481984 000001000000000000000000000000000000000000000000000000000000
36028797018963968 000010000000000000000000000000000000000000000000000000000000
72057594037927936 000100000000000000000000000000000000000000000000000000000000
144115188075855872 001000000000000000000000000000000000000000000000000000000000
288230376151711744 010000000000000000000000000000000000000000000000000000000000
576460752303423488 100000000000000000000000000000000000000000000000000000000000
now if we take these values in array and bitwise OR of all of them answer is unique -
which is
1152921504606846975 111111111111111111111111111111111111111111111111111111111111
Now if we do bitwise OR then the value is already present in set , so no change , means answer will be NO
else for size less than 60 we will do brute force bcz answer may or may not exist .
See this guy solution : HERE
8 Likes
Include me in this list 
can someone make me understand why this is in testers solution
Blockquote
if (n >= 100) {
cout << “NO\n”;
why would be the answer NO if the number of element is more than 100 ?
1 Like
His variable names though LMFAO XD
1 Like
Thanks for the reply. What if the array consists of value 1 2 3 4 5 … 64 how does this work?
Yeah he is known for doing that
Can anyone explain this python solution?
I’m really curious to know…
https://www.codechef.com/viewsolution/35815848
Same as gfg 
Wooooaaahh… That’s bit too much of ‘same’
Wow, This solution is really cool. It’s like pigeon hole theory.
So, We can claim that there will be at least 2 numbers whose bits will be common, if numbers are >= 62.
1 Like
Suppose you can have only 10 bits numbers, then first number should have atleast one set bit, then second number should add some distinct bit so Or of first two should have atleast two set bits and so on so Or of first set bit should have atleast 10 set bit (ie every possible bit is set in Or of first ten numbers). Then whatever be the 11th number, it’s set bits are already set in Or of first ten numbers . So for all ORs to be distinct N can not be greater than number of bits possible.
according to u loop will run till 64 times in worst case bt according to tester after 60 it will terminate… hope u understand what i am trying to say
def cal(l):
res = set()
p = {0}
for k in l:
p = {y|k for y in p} | {k}
res |= p
return len(res)
t = int(input())
for i in range(t):
n = int(input())
l = [int(j) for j in input().split()]
le = cal(l)
‘’’
check for duplicate entries which will make the set length less than the total number of possible (l,r) pairs
‘’’
if le == n*(n+1)/2:
print(“YES”)
else:
print(“NO”)
Much better explained in GFG
Can someone give a firm explanation or proof for this approach?
Although it seems intuitive, I am not able to digest why this always works.