Number of subsequence's with same values of bitwise and, or and xor

Question

GeeksForGeeks

We are given an array arr of $n$ element. We need to count number of non-empty subsequences such that these individual subsequences have same values of bitwise AND, OR and XOR. For example, we need to count a subsequence (x, y, z) if (x | y | z) is equal to (x & y & z) and (x ^ y ^ z). For a single element subsequence, we consider the element itself as result of XOR, AND and OR. Therefore all single element subsequences are always counted as part of result.

The editorial for the above problem states:

1. If there are $n$ occurrences of zeroes in the given array, then will be $2^{n} - 1$ subsequences contributed by these zeroes.
2. If there are $n$ occurrences of a non-zero element $x$, then there will be $2^{n-1}$ subsequences contributed by occurrences of this element. Please note that, in case of non-zero elements, only odd number of occurrences can cause same results for bitwise operators.

I am not able to understand the proof for the statement Please note that, in case of non-zero elements, only odd number of occurrences can cause same results for bitwise operators.

Can anyone help me understanding why this works?

Answer 1

x & y & z == x | y | z if either all three of x, y and z are 1 or if all three are 0. The same obviously for 1, 2, 4, 5, 6 etc. numbers.

If all items are zero, then x ^ y ^ z is also zero, so you include all subsequences made of all zero.

If all items are one, then the xor of an even number of 1's is zero, and the xor of an odd number of 1's is 1. It matches the logical "and" or "or" if and only if the number of items is odd. So you include all subsequences made of an odd number of 1s.