Ad hoc, counting
Given N bits (where a bit is either a 0 or a 1), how many ways can I remove exactly one number so that the XOR of all the N-1 remaining numbers is zero?
Let C be the number of 1 bits in the input. Then the answer is C if C is odd, and N-C otherwise. Note that N-C is the number of 0 bits in the input
First, note that the XOR or two bits is 0 if they are equal, and 1 if they are not equal. From this, one can deduce that the XOR of N bits is 1 if there are an odd number of 1 s present, and 0 otherwise. This can be easily seen by noticing that XOR is associative, and that the running XOR changes/flips whenever a 1 is encountered. Since the running XOR starts at 0, we thus want the number of 1 s to be even for the XOR to be 0.
Let C_1 and C_0 be the number of 1 s and 0 s in the input. Note that these numbers are easy to compute by a single scan of the entire input. However, you can just compute one of them, say C_1, because you can get the other by noting that C_0 + C_1 = N (so C_0 = N - C_1). We will handle two cases, depending on whether C_1 is even or odd.
- If C_1 is odd, then we should remove a 1, because removing a 0 does not change the parity of C_1. In this case, there are C_1 ways to remove exactly one number so that the XOR of all the N-1 remaining numbers is zero (because there are C_1 1 s!).
- If C_1 is even, then we should remove a 0, because C_1 is already even. In this case, there are C_0 ways to remove exactly one number so that the XOR of all the N-1 remaining numbers is zero (because there are C_0 0 s!).