0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The editorial contains no proofs, so it's not surprising that you can't understand them; they're just not there. $\endgroup$ Oct 21, 2021 at 12:38
  • $\begingroup$ 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? $\endgroup$
    – greybeard
    Oct 21, 2021 at 14:46

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.