Neighboring Bitwise XOR

Leetcode Problem:

• Neighboring Bitwise XOR

Summary

• This problem is about determining whether a valid binary array can be formed from a given derived array.

Approach

• The approach used in the solution is to create a new array called original and fill it with the XOR of adjacent values in the derived array
• Then, check if the first and last elements of the original array are equal, which means a valid binary array can be formed from the derived array.

Complexity

• O(n) where n is the length of the derived array

Explanation

• The solution starts by pushing the first element of the derived array to the original array
• Then, it iterates over the derived array and pushes the XOR of the current element and the last element of the original array to the original array
• Finally, it checks if the first and last elements of the original array are equal, which means a valid binary array can be formed from the derived array.

Solution Code:

class Solution {
public:
    vector original;
    bool doesValidArrayExist(vector& derived) {
        int N = derived.size();
        derived.push_back(derived[0]);
        original.push_back(derived[0]);
        for(int i = 0 ; i < N; i++){
            original.push_back(derived[i] ^ original[i]);
        }
        return original[0] == original[N];
    }
};