## PROBLEM LINK:

## DIFFICULTY:

Easy-Medium

## 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**has exactly 1 bit as 1 and all other bits are

_{i}0. Also as

**N**>= 130, we’ve at least 65 values of

**x**. Note all of them can

_{i}be distinct as each

**x**has only 1 bit set and all x

_{i}_{i}are at maximum 64 bits

long. So say

**x**for some

_{j}= x_{k}**j**and

**k**

Then **x _{j} xor x_{k} = 0**

=>

**A(2j) xor A(2j+1) xor A(2k) xor A(2k+1) = 0**

And so the answer is YES.

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.**

Then **A[i1] xor A[i2] xor A[i3] = A[i4]**

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.

```
for i in 1 to N
for j in i+1 to N
for k in j+1 to N
x = A[i] ^ A[j] ^ A[k]
if A[k+1...N] contains x, return true
return false
```

**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.