Skip to content

← leetcode

Neighboring Bitwise XOR

· Medium

LeetCode problem 2683

The trick to this question is to realise that if, for example, [0, 1, 0] is a valid original array, then consequently, [1, 0, 1], is also a valid original array.

This means that you can set original[0] as either 0 or 1; the only requirement is that when you reach the last element (let that be at index position n), that
derived[n-1] = original[n-1] ⊕ original[0].

In my algorithm, I decided to select original[0] = 0. Then, we iterate through the derived array, calculating original[i+1] at every step with derived[i] ⊕ original[i] as we know derived[i] ⊕ original[i] = (original[i] ⊕ original[i+1]) ⊕ original[i] = original[i+1].

Then, once we reach i = n, since original[0] = 0, we know that derived[n-1] = original[n-1] ⊕ original[0] is equivalent to derived[n-1] = original[n-1], so we just need to prove for equality between the two elements to verify if an original array exists.

code

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int prev = 0;
        for (int i = 0; i < derived.size()-1; ++i) {
            prev ^= derived[i];
        }
        return derived[derived.size()-1] == prev;
    }
};

complexity

  • time: O(n)
  • space: O(1)