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

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?

• The editorial contains no proofs, so it's not surprising that you can't understand them; they're just not there. Commented Oct 21, 2021 at 12:38
• The results of $AND$ and $OR$ equal the "input value(s)" only if all have the same value. For 0/false, that will be the result of $XOR$, too - how about 1/true? Commented Oct 21, 2021 at 14:46