Today’s problem

https://leetcode.com/problems/neighboring-bitwise-xor/description/

Intuition

  • Based on the information of yesterday’s problem, we know that $a\space xor\space a = 0$.
  • Therefore, $\large{XOR}_{i=0}^{n} \small derived[i]$ has to be 0, because all the $original$ offsets. Here, n means the last index of the sequence.
  • Now lets prove that if $\large{XOR}_{i=0}^{n} \small derived[i] = 0$ enables us to create the whole $original$ sequence.
  • Let $original[0]=0$, $original[k] = original[k-1]\space xor\space derived[k]$.
  • Now all we need to prove is $original[n]\space xor\space original[0]=derived[n]$, that is, $original[0] = original[n]\space xor\space derived[n]$.
  • According to the formular above, $original[n] = \large{XOR}_{i=0}^{n-1} \small derived[i]\space xor\space original[0]$
  • Because $\large{XOR}_{i=1}^{n} \small derived[i] = 0$,
  • so $original[n]\space xor\space derived[n] = original[0]\space xor\space \large{XOR}_{i=0}^{n} \small derived[i] = 0 = original[0]$.
  • Therefore, this sequence of $original$ is valid.

Trick

  • Now we want to know whether the sequence itself has a xorsum 0 or not. Now, because it is a binary sequence, we can put all 0s together and 1s together, so that now by xor all the 0 and 1s, we find that the result is just the count of 1s. If the count is odd, then the result would be 1, otherwise it would be 0.
  • Therefore, the easiest way to solve this question is to sum up everything in the sequence and check whether it is odd or even.

Approach

Sum up everything in the sequence and check whether it is odd or even.

Complexity

  • Time complexity: $O(N)$, N is the length of the sequence.

  • Space complexity: $O(1)$, no other variables stored.

Code

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        return (sum(derived) & 1) == 0

image.png