.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 XOR-out to the same value: 00000000000001000000000000
that will form the quadruple that gives zero isn’t it ?
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?
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))
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.
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!
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.
