# Problem Link:

**Author** Roman Furko

**Tester** Balajiganpathi

**Editorialist** Utkarsh Lath

# Difficulty:

easy

# Pre-requisites:

Tries

# Problem:

Given a list of numbers, you have to choose 3 of them so that xor of the chosen numbers is maximal

# Explanation:

The most obvious way to solve this problem would be to find xor of all triplets of elements in the list and report the maximum. Complexity of such a solution is **O(N^3)**. This solution will be able to solve subtask 1 with **N ≤ 100**. However, for larger **N**, it will take too much time, and should time out.

Lets try to find if the problem can be solved in smaller time. Lets look at each nmber as a bitstring of length 30. Lets say we fix two numbers **X** and **Y**, and we want to find the third number **Z ≠ X, Y** such that **X xor Y xor Z** is largest. Let **W = X xor Y**. **W** is also a bitstring of length 30. We want to choose a **Z** so that XOR of **W** and **Z** is maximum.

Lets consider the possibilities of **Z**. If the first bit of **W** is **w _{1}**, we want the first bit of

**Z**to be

**1 ^ w**, so that the first digit of XOR be 1. If there exist any such

_{1}**Z**, then only those

**Z**s need to be consider further, because for any other

**Z**, the XOR will always be less than

**2**. Similarly, if

^{29}**w**is the second bit of

_{2}**W**, then we would prefer to have the second bit of our best

**Z**to be

**1 ^ w**. If such a

_{2}**Z**exists among the list of

**Z**s being currently considered then the second bit of optimal XOR is 1. Also, we will choose only those

**Z**s for next step for which second bit is

**1 ^ w**. If not, all the

_{2}**Z**are equally bad and we will not remove any of the

**Z**s. We can keep going like this, maintaining the list of possible

**Z**s all the time till all

**30**bits of the optimal XOR have ben decided.

The only hard part about this solution is to maintain the set of possible value of **Z**, as we examine every bit of **W**. This can be done easily by maintaining a Trie of all values of **Z ≠ X, Y**. We start with current node = root node of this trie. At any time, the set of values of **Z** we are considering are the descendants of current node. To test whether there exists any **Z** for which **i ^{th}** bit is

**b**would be same as testing whether the current node has a non-null child along edge corresponding to

**b**. To choose only those

**Z**s for which

**i**bit is

^{th}**b**would be same as going one step towards edge corresponding to

**b**. The complexity of this solution is

**O(N**, and can be used to solve all subtasks. See Tester’s / Setter’s solutions for implementation details.

^{2}log A_{max})