A non-negative integer with 64 bits can differ to at most 63 nos by 1 bit (i.e. have exactly one different digit in their binary representation.). Now, suppose, N<68. Suppose, N is 67. Now, in the sequence repetition of one element is allowed i.e. if an element a exists in the input number sequence, then it can be repeated and it can be repeated upto 3 times (allowed without making the XOR of 4 nos zero). Because, if the no. is repeated >=4 times then clearly it’s over. (a,a,a (a is an element of the sequence which is repeated) and a will be chosen for XOR operation and result will be zero) Now, why repetition of only one element is allowed? Because, if two elements (say a and c) are repeated in the sequence (twice or more than twice does not matter) there will be always four elements in the sequence for which xor operation will result zero. (a,a,c,c) . Now, if N is 67 (or less than 67) then we can choose only one a among two or three a’s to try for a solution of this problem (if we choose two a or three a in the solution then solution will never be achieved. Think about it. If we choose a,a,b,c (where a,b and c are distinct elements) for a solution then a^a (^:- bitwise XOR) is zero. And the resulting solution (xor of 4 elements) will never be zero unless b=c. But it is a contradiction. since repetition of only one element is allowed) So, now it’s clear, why we can only choose one a from the repetitions for achieving the desired solution. Now deduce 3 from 67, result is 64 and these 64 elements are distinct. So, 64 distinct elements and one a, from which we can create only 64 pairs. (and remember, 64 distinct pairs are possible between adjacent elements ). Now, why we are only allowing the pairs of adjacent elements (like, in the example test cases such pairs are (1,0), (0,2), (2,3) and (3,7)) because, their resulting xor pair has only one bit turned on. (only one bit is set) that is why for N<=67 the result can be “NO”. but for N>=68, we can have 66 distinct elements and 65 such pairs. among these 65 pairs, two pairs have to be same (according to the pigeonhole principle). That’s why, for N>=68 result will always be yes.
Solved in O(n^2) time complexity
I had the same algorithm initially, but i believe test data was not correct at that time. Then i switched to pigeonhole.
I think that you can always test input with assert statement in C/C++ and if your check fail you will get SIGABRT instead of WA, so you can write your feedback…
Yeah i know. But somehow at that time, i wasn’t convinced with this algorithm and pigeonhole was another idea in my mind. So i stopped thinking too much about it 
oops sorry something gone wierd please refer to the solution at CodeChef: Practical coding for everyone and tell me for what cases it goes wrong…
it returns no for
6
2 3 2 6 14 6such a luck :-/
@author + tester: is there test case where correct tuple are numbers with indexes 64, 65, 66, 67 ? It should get TLE…
try this… 2 0 2 3 2 6 2… it has “2 xor 2 xor 2 xor 2 = 0”… Is ur algo right for this?
yeah it works. output is “yes”.
This is just a tip, but you should use %lld instead of %I64d, maybe this is the problem (it’s written in help).
I think that @saurabhmodi102000’s description is clear about this…
If not, try to find sequence where xors are A, A, B, B, C, C, such sequence is A = { 2, 3, 2, 6, 2, 10, 2 }, but if you choose 4 times 2 the result is 0.
Thanks for the tip, but it still gets WA.
That is the logic behind the O(n) solution, but there are corner cases to consider. See the first post.
sorry for confusion I meant %llu in this case, now it should work fine
anyway, I’m still interested in counter example…
I have a problem… The problem gets Accepted everytime I submit your solution… However if I write my own Brute Force code and submit it it gives TLE… Any clues why?
you are using long long instead of unsigned long long, when I removed unsigned I got TLE, but I have no idea why…
Note : n < 2^64, so using signed long long changes the numbers(due to overflow), and this violates the property mentioned in the problem.(maybe due to which program is unable to find a solution and run in O(n^4))
here is the counter example
5
9223372036854775808
9223372036854775809
9223372036854775810
9223372036854775812
9223372036854775816Wow it got accepted now! I didn’t know there was a different specifier for unsigned long long. Thanks!