17_Neighboring_Bitwise_XOR.cpp

// 2683. Neighboring Bitwise XOR

// A 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.

// Specifically, for each index i in the range [0, n - 1]:

// If i = n - 1, then derived[i] = original[i] ⊕ original[0].
// Otherwise, derived[i] = original[i] ⊕ original[i + 1].
// Given an array derived, your task is to determine whether there exists a valid binary array original that could have formed derived.

// Return true if such an array exists or false otherwise.

// A binary array is an array containing only 0's and 1's
 

// Example 1:

// Input: derived = [1,1,0]
// Output: true
// Explanation: A valid original array that gives derived is [0,1,0].
// derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
// derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
// derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0
// Example 2:

// Input: derived = [1,1]
// Output: true
// Explanation: A valid original array that gives derived is [0,1].
// derived[0] = original[0] ⊕ original[1] = 1
// derived[1] = original[1] ⊕ original[0] = 1
// Example 3:

// Input: derived = [1,0]
// Output: false
// Explanation: There is no valid original array that gives derived.
 

// Constraints:

// n == derived.length
// 1 <= n <= 105
// The values in derived are either 0's or 1's


// Approach 1: Simulation

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

        bool checkForZero = (original[0] == original[original.size() - 1]);
        original = {1};
        for (int i = 0; i < derived.size(); i++)
        {
            original.push_back((derived[i] ^ original[i]));
        }
        bool checkForOne = (original[0] == original[original.size() - 1]);

        return checkForZero | checkForOne;
    }
};

// Approach 2 : Cumulative XOR

class Solution
{
public:
    bool doesValidArrayExist(vector<int> &derived)
    {
        int XOR = 0;
        for (auto element : derived)
        {
            XOR = XOR ^ element;
        }
        return XOR == 0;
    }
};

// Approach 3: Sum Parity

class Solution
{
public:
    bool doesValidArrayExist(vector<int> &derived)
    {
        int sum = accumulate(derived.begin(), derived.end(), 0);
        return sum % 2 == 0;
    }
};

/*
Approach 1 (Simulation):
- We try to construct the original array starting with both 0 and 1
- For each value, we use XOR to determine the next value in original array
- If either attempt results in a valid circular array (first = last), return true

Approach 2 (Cumulative XOR):
- Key insight: XORing all values in derived array must equal 0 for a valid solution
- This is because each original[i] appears twice in XOR operations
- Double XOR of same value cancels out, so total XOR must be 0

Approach 3 (Sum Parity):
- Related to XOR property - sum of 1s in derived must be even
- This is because each 1 in original contributes to two positions in derived
- Therefore total number of 1s in derived must be even for a valid solution
*/