PROBLEM LINK:DIFFICULTY:EasyMedium PREREQUISITES:Pigeonhole Principle, Sets PROBLEM:You're given N 64 bit integers such that any two successive numbers differ at exactly 1 bit. Your job is to find out if there are 4 integers such that their xor is equal to 0. QUICK EXPLANATION:Whenever N >= 130, it is always possible to find 4 integers of the given list such that their xor is 0. For smaller N, one could do an exhaustive search in O(N^3 log N). DETAILED EXPLANATION:Solution of this problem is simpler than many of you might've imagined. For all N >= 130, answer is always YES. Let's see why : Assume there are >= 130 numbers in input array A. Let x_{i} = A[2i] xor A[2i+1] for i in [0, N/2) As any two successive values of A differ at exactly one bit, binary representation of each x_{i} has exactly 1 bit as 1 and all other bits are 0. Also as N >= 130, we've at least 65 values of x_{i}. Note all of them can be distinct as each x_{i} has only 1 bit set and all x_{i} are at maximum 64 bits long. So say x_{j} = x_{k} for some j and k Then x_{j} xor x_{k} = 0 Small Case: What if N < 130? We could do an exhaustive search. One could try moving all 4 numbers and see if their xor is 0 or not. This takes O(N^4) time and is probably too costly. We can do this in O(N^3 log N) as well. Let's see how. Say if there are four indices i1, i2, i3, i4 such that
A[i1] xor A[i2] xor A[i3] xor A[i4] = 0. So we could move over all three numbers of array, find their xor and check if it is present in set as well or not.
Note : Actually 130 is only an upper bound. We don't have a case for N > 67 for which answer is No. Maybe such a case doesn't exist and our proof given above could be strengthened. If you have a case where N > 67 and answer is NO, please share it here. SETTER'S SOLUTION:Can be found here. TESTER'S SOLUTION:Can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 11 Jul '12, 15:43

I solved this in O(N): for each i in 0..N1 I found B[i] = A[i] xor A[i+1]  there are only 64 possible values (2^{0}, 2^{1}, 2^{2}, ..., 2^{63}), the question is if there are two same values in B. There are three corner cases in this approach:
answered 11 Jul '12, 16:14
I had the same algorithm initially, but i believe test data was not correct at that time. Then i switched to pigeonhole.
(11 Jul '12, 17:15)
1
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...
(11 Jul '12, 17:25)
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 ;)
(11 Jul '12, 17:33)
@javadecoder: is there something incorrect in my post?
(17 Jul '12, 19:23)

There is a proof for N >= 69 that answer shall always be yes. Also,the limit on N can probably be reduced further. See, consider N = 69.Now,there are 68 possible pairs for N = 69. Obviously,by pigeonhole principle,there has to be 2 pairs definitely,the xor of whose elements is same. Now ,consider such two pairs.One of the two things could happen. 1)The pairs could be overlapping,i.e,they have a common element,for instance 1,3,1.Here,(1,3) and (3,1) are two possible pairs. 2)There could be two disjoint pairs that have same xor values in which case we need not go further and have the answer with us. Now ,if we encounter case 1), we can first remove these 3 numbers,and now we are left with 66 numbers.Now,we have 65 pairs.Again ,the situation similar to above shall happen,i.e. one of the two situations shall occur. Now if the situation 2 occurs,we need not go further,but if situation 1 happens,then that means that we have another triplet. The first triplet was of the form,  a,b,a and the 2nd triplet was of the form  c,d,c. the xor of a,a,c,c is 0.Therefore,we always have answer " yes" for number >= 69. answered 11 Jul '12, 18:01

Simple Brute Force : http://www.codechef.com/viewsolution/1176364 answered 11 Jul '12, 22:12
such a luck :/ @author + tester: is there test case where correct tuple are numbers with indexes 64, 65, 66, 67 ? It should get TLE...
(11 Jul '12, 23:05)
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?
(13 Jul '12, 16:08)
you are using
(13 Jul '12, 17:08)
2
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))
(13 Jul '12, 17:56)

I don't know about the formal proof for N > 67, but for N = 67, we can have 'NO' cases because pairs of adjacent elements can have the same XOR value, but those adjacent elements cannot form the answer, as they have an element in common. For eg take 3 numbers: a,b,c : such that a xor b = b xor c , but our answer cannot be yes here, because b is taken twice. I hope the following example can save my shoddy explanation. A concrete example, for 5 digit binary numbers (numbers upto 2^5  1). As betlista mentioned, we can only have 5 possible Xor values: 1,2,3,4,5. If the xor values for adjacent pairs repeat, we have the answer YES, except for cases, where neighboring xor values are equal. Here is a case where there are 2 pairs of equal xor values ( 8 elements in total ), but the answer is still NO. 10001 , 10000, 10001, 10011, 10001, 10101, 11101, 01101 10001 xor 10000 = 1, 10000 xor 10001 = 1, 10001 xor 10011 = 2, 10011 xor 10001 = 2, 10001 xor 10101 = 3, 10101 xor 11101 = 4, 11101 xor 01101 = 5 So for 5 digits, we have a sequence of 8 numbers for which the answer is NO. Similarly for 64 bit binary numbers , we can make a case upto N == 67, where the answer is NO, but we can't go higher than 67. In the example , I could put in only 2 pairs of XOR values that were repeated, i.e 1 and 2. Whenever I tried to make a case with 3 pairs, the answer would automatically be YES, because in making the third pair, I would have to put in a number in the sequence, which had already come before. answered 11 Jul '12, 17:55

the result will be 0 for n>=67.. Proof: there 64 bits possible @max. let i1,i2,i3,..... be the eles. Take the first pair (i1&i2) and XOR them. The result will look like this 0000000001000000000000000000000000000000000.. 64 bits Xor i3&i4,i4&i5,.......,i66&i67 Any of these results will surely have the result mentioned above by pigeonhole principle. answered 15 Jul '12, 18:00

I cldn't compete this month due to exams:( but kudos to the setter of this problem. I love its analysis, especially the proposed O(n) solution. big ups! answered 17 Jul '12, 04:52

Please anyone tell me for which cases my code for this problem gives WA
I considered xor of every adjacent element and increased the count of the b[65] array corresponding to the bit which was set but eeping in mind that there are not 2 such consequtive cases such that a^b==b^c for that previous,now and l variable are used..as soon as we get an array with count>1 it means that we have found out 2 such pairs such that a^b==c^d and all are distinct too..basically i concentrated on the unique set bit on xoring two gray like numbers and found out if there is a count increase of not...for the pigeonhole proof it comes from here that suppose we have a series such that a^b==b^c such that every 3 consequtive numbers share a singe xor answer thus a^b and b^c give a particular set bit,c^d and d^e give another particular set bit position and so on if it goes like this then all the 64 bits would be covered in at max to max 2n+1 cases where n are the total bits in a number which for here gives 129 according to my calculations for which the admin is probably right in giving limit<=130. answered 11 Jul '12, 18:42
oops sorry something gone wierd please refer to the solution at http://www.codechef.com/viewsolution/1170413 and tell me for what cases it goes wrong..
(11 Jul '12, 18:46)
1
it returns no for
(11 Jul '12, 18:50)

I had O(n^2 log n) solution and got accepted! Pigeonhole must have reduced actual runtime! My solution checks for: a[i1] xor a[i2] == a[i3] xor a[i4], by keeping each pairwise xor in a multimap to ensure unique indexes.
answered 11 Jul '12, 21:51

I am dying to know why this solution gets WA http://www.codechef.com/viewsolution/1176713. For every two adjacent numbers I find which bit changes and count how many times each bit changes. Then if any bit changes twice but not consecutively the answer is yes. I spent hours trying to debug this and trying every case I could possibly think of. It also handles all the cases mentionned above, but still gets WA. Eventually I recoded the exact same algorithm in Python and got AC http://www.codechef.com/viewsolution/1152313. So could anyone please tell me what the problem is? answered 11 Jul '12, 23:21
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?
(12 Jul '12, 00:25)
yeah it works. output is "yes".
(12 Jul '12, 00:57)
This is just a tip, but you should use %lld instead of %I64d, maybe this is the problem (it's written in help).
(12 Jul '12, 14:01)
Thanks for the tip, but it still gets WA.
(12 Jul '12, 23:07)
1
sorry for confusion I meant %llu in this case, now it should work fine ;) anyway, I'm still interested in counter example...
(13 Jul '12, 13:56)
here is the counter example
(13 Jul '12, 18:25)
Wow it got accepted now! I didn't know there was a different specifier for unsigned long long. Thanks!
(13 Jul '12, 19:30)
showing 5 of 7
show all

According to me the upper bound should be 130 only. For this suppose A[0] and A[1] differ in 1st least significant bit so their xor would be only 1, A[1] and A[2] also differ in 1st bit so their xor would also be 1. Similarly A[2] and A[3] xor is 10 and A[3] and A[4] xor is also 10. So for each bit set we can have three adjacent numbers and two pairs (firstsecond and secondthird). Thus for 64 bits we can have 64*2+1= 129. thus if N>=130, we would always have YES otherwise we can have NO :) answered 12 Jul '12, 10:43
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
(12 Jul '12, 14:08)

Can anyone tell me why this logic fails ? .Since two adjacent numbers differ by a single binary bit, the result of XOR'ing two adjacent numbers together is very predictable x represents a bit whose value doesn't matter, but is the same as the corresponding x below/above it. xor: xxxxxxxxxxxxx1xxxxxxxxxxxx xxxxxxxxxxxxx0xxxxxxxxxxxx 00000000000001000000000000 This is true for ANY two adjacent numbers in the array so now if i can find another pair of adjacent numbers, that differ by the same bit, they will ALSO XORout to the same value: 00000000000001000000000000 that will form the quadruple that gives zero isn't it ? answered 13 Jul '12, 00:29
That is the logic behind the O(n) solution, but there are corner cases to consider. See the first post.
(13 Jul '12, 08:07)
@neil_812 :thanks
(15 Jul '12, 18:03)

Is it too late to post an answer on this problem? There is a time limit or we can discuss it at length on community? This is my first time here. Danel Sorescu Web Developer locuri de munca in strainatate answered 30 Aug '12, 11:08

A nonnegative 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. answered 18 Jun '14, 01:16

Solved in O(n^2) time complexity http://www.codechef.com/status/GRAYSC,krodhking answered 27 May '15, 19:14
