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?
QUICK EXPLANATION:
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
EXPLANATION:
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_11 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_00 s!).
If there is a test case with 1 1 0 0 even no. of ones and even no. of 0s then output would be 2 according to the editorial?
But answer shouldn’t be zero?
@vishveshcoder the answer should be 2 for your sequence as overall the xor is 0 currently if you remove any of the 1’s the xor will become 1. You could also arrive at this fact by realizing the fact that xor is self inverse.
For information
0^0 is 0
0^1 is 1
1^0 is 1
1^1 is 0
xor is associative and commutative.
0 is identity element for xor
if number of 1’s is even the overall value is 0 already so you can remove only 0’s. If number of 1’s is odd the overall value is 1 and you can remove only 1’s to get to zero.
Hope this helps.
Please upvote if you find it useful.
The question says in how many ways we can remove exactly one bit so that the XOR of all the N−1 remaining bits is zero, in the above example 1 1 0 0, the answer would be 2 because removing any of the two zeroes would give the answer as 0. So the question is not that whether we need to remove any bit or not and if so in how many ways rather it says in how many ways exactly one bit you can remove to get the answer as 0.
I thought that the XOR would be zero only if every number would be equal. I didn’t understand the definition well. Those 2 examples fit in my wrong definition, maybe that’s why I got it wrong. It’s my fault tho.
@agua1 1 ^ 1 ^ 0 ^ 0 is 0 initially, now if we remove exactly 1 zero (say a[2] ) than it becomes 1 ^ 1 ^ 0 which is still zero similarly for other 0 (a[3]) could be removed (^ means xor here). So what i want to say is if we calculate the initial xor (which is equivalent to counting if no of ones is even or odd) we can easily know the xor after removing Exactly one element or in other words we know whether i can remove zero or one.
