# DCP-475: Bunty's Xor Game Back to All Problems

Hard Divide and Conquer > Dynamic Programming

As you know, **Bunty** loves playing with numbers. He is now playing a game with his sister. Initially there is an array of N integers. They play the game in turns. **Bunty gives the first move**. In each move, one can choose two numbers from the array and score of this turn is the xor of the two numbers. After each turn, player removes the selected two integers from the array. The game continues until the array is empty. Now Bunty wants to know , what is the maximum score he can obtain. Note: Both of them play optimally well i.e Bunty's sister always plays in such a way that will make score of Bunty lesser and Bunty tries to maximize his score as much as possible. The Final Score of Bunty is the sum of all round played by Bunty Input: ------ Input starts with an integer **T (1<=20)**, denoting the number of test cases. Each case contains an integer **N ( 2≤ N ≤ 16)** denoting the number of elements of array A. N will be always even. Then in the next line there are N non-negative integers **(0 <= Ai <= 10^9)** Output: ------- For every test case, output the maximum score Bunty can obtain if both play optimally. Sample Input ------------ 1 4 1 2 4 3 Sample Output ------------- 7

### Problem Limits

 Language Time Limit (seconds) C 2.00 C++ 2.00 C++14 2.00 C# 2.00 Go 2.00 Java 4.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 4.00 Python3 4.00 Ruby 2.00 VB.Net 2.00

# 35/223

Solve/Submission

### Ranking

# User Language Timing
01 Robbinb1993 Cpp14 0.29s
02 amin21 Cpp 0.51s
03 Morass Cpp14 0.51s
04 kzvd4729 Cpp14 0.54s
05 mahbubcseju Cpp 0.55s
06 ovis96 Cpp14 0.57s
07 Hasinur_ Cpp 0.59s
08 Tahmid Cpp14 0.74s
10 Trumen Cpp 0.85s
11 ksohan Cpp 0.92s
12 Dayamoy Cpp14 0.95s
13 njrafi Cpp 0.97s
14 CLown1331 Cpp 1.04s