407290: GYM102756 E Hieroglyph Sequences

Sylvia has been fascinated with Ancient Egypt and used her brand-new time machine to go back in time to the era of her favorite king, Ramses II. While King Ramses II was a highly successful leader, he was also highly eccentric and during her adventures, Sylvia found out that he had a very particular property that all hieroglyph sequences should follow in order for him to read it.

Each hieroglyph in the alphabet was assigned a unique number and King Ramses only accepted the message if the bit-wise XOR of all the numbers in the sequence was equal to $$$0$$$. Unfortunately, Sylvia did not know this before traveling back in time so she doesn't know if the message that she wrote for him satisfies his eccentric request. She also doesn't have too much time before her meeting with the King. Thus, she decides she will replace the minimum hieroglyphs possible in order to make the sequence fit his constraints. Given the numerical representation of the hieroglyphs that Sylvia has written, help her figure out the minimum number of elements in the sequence that need to be replaced in order to make the bitwise XOR of the sequence equal to $$$0$$$.

Note: The XOR between two bits is defined as a function that returns 1 if exactly one of the bits is a 1 and 0 otherwise. The bitwise XOR between two numbers is applying the XOR function on each of the corresponding bits (the last bit of the output is the XOR between the last bits of each of the input numbers and the second-to-last bit of output is the XOR of second-to-last bits of input and so on).

The first line of input will be a single integer $$$n$$$ (where $$$2 \leq n \leq 10^4$$$).

The second line of input will contain $$$n$$$ space-separated integers representing the elements in the sequence where $$$1 \leq h_i \leq 10^9$$$.

Output a single integer representing the minimum number of elements in the sequence that need to be replaced in order to make the bitwise XOR of the sequence equal to 0.

3
2 4 8

1

4
1 1 1 1

0

In the first sample test case, we can replace the first element with a 12 and then the bitwise XOR of the elements in the sequence is zero so the answer is 1. In the second test case, the bitwise XOR of the elements is already zero so the answer is 0.