XOR and the Array
Given an array of N integers, you need to find out the minimum number of integers that must be added to the array such that for each integer of the array, there is at least one other integer in the array such that their bitwise XOR is 0.
Input
The first line of the input contains a number N (1 ≤ N ≤ 105) denoting the size of the array. The next line contains N space separated positive integers, Ai (0 ≤ Ai ≤ 109) denoting the integers of the array.
Output
In a single line, print the minimum number of integers that must be added to the array.
Samples
| Input | Output |
|---|---|
3 5 2 5 | 1 |
| Input | Output |
|---|---|
4 8 3 1 8 | 2 |
Note
Here is the XOR table if you are not familiar with it:
| x | y | x XOR y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
While computing the XOR value of two numbers, each bit of the output will be the XOR of the corresponding bits of those two numbers. In most programming language (including C, C++, Python and Java), bitwise XOR operator is denoted by "^" (without the quote). So if you have two numbers called x and y, their bitwise XOR will be denoted by x^y.
