Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

XOR and the Array

By Sherlock221b · Limits 1s, 512 MB

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

InputOutput
3
5 2 5
1
InputOutput
4
8 3 1 8
2

Note

Here is the XOR table if you are not familiar with it:

xyx XOR y
000
011
101
110

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.

Discussion

Statistics


83% Solution Ratio

ewuintra2016.14$6neZAEarliest, Nov '16

mosiurFastest, 0.0s

ewuintra2016.19$C3WodLightest, 524 kB

habijabiShortest, 267B

Submit

Login to submit

Editorial

The XOR value of two numbers can only be 0 if the numbers are same. Therefore, all you have to do is...

Toph uses cookies. By continuing you agree to our Cookie Policy.