Scale Engineer

Neighboring Bitwise XOR

Med
#2432Time: O(n). We iterate through the `derived` array to construct the `original` array. This is done at most twice, resulting in a linear time complexity.Space: O(n). We allocate an auxiliary array `original` of size `n` to store the constructed binary array.
Patterns
Bit Manipulation
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the observation that the entire original array is determined if we know the value of its first element, original[0]. Since original is a binary array, original[0] can only be 0 or 1. We can try both possibilities and check if either leads to a valid solution.

Algorithm

  • Try original[0] = 0:
    • Create a candidate original array of size n.
    • Set original[0] = 0.
    • Calculate the remaining elements original[1], ..., original[n-1] using the recurrence original[i] = original[i-1] ^ derived[i-1].
    • Check if derived[n-1] == original[n-1] ^ original[0]. If true, return true.
  • Try original[0] = 1:
    • If the first try failed, repeat the process with original[0] = 1.
    • If the final check is successful, return true.
  • No Solution:
    • If both tries fail, return false.

Walkthrough

This approach directly simulates the process of constructing the original array. The key insight is that if we fix the value of original[0], all other elements original[i] are uniquely determined by the recurrence relation original[i+1] = original[i] ^ derived[i]. Since original[0] must be either 0 or 1, we have only two cases to check.

We can write a helper function that takes a potential starting value for original[0], constructs the full original array, and then checks if this constructed array satisfies the final, wrap-around condition: derived[n-1] == original[n-1] ^ original[0]. If the check passes for either starting value (0 or 1), we have found a valid solution.

class Solution {    public boolean doesValidArrayExist(int[] derived) {        // Helper function to check a given starting value for original[0]        if (check(derived, 0)) {            return true;        }        // If starting with 0 fails, try starting with 1        if (check(derived, 1)) {            return true;        }        return false;    }     private boolean check(int[] derived, int firstElement) {        int n = derived.length;        int[] original = new int[n];        original[0] = firstElement;         // Construct the rest of the original array        for (int i = 0; i < n - 1; i++) {            original[i + 1] = original[i] ^ derived[i];        }         // Check if the last element relationship holds        // derived[n - 1] = original[n - 1] ^ original[0]        return (original[n - 1] ^ original[0]) == derived[n - 1];    }}

Complexity

Time

O(n). We iterate through the `derived` array to construct the `original` array. This is done at most twice, resulting in a linear time complexity.

Space

O(n). We allocate an auxiliary array `original` of size `n` to store the constructed binary array.

Trade-offs

Pros

  • It's a direct simulation of the problem statement, making it intuitive to understand.

  • It correctly solves the problem by exhaustively checking the only two possible scenarios.

Cons

  • Uses O(n) extra space to store the candidate original array, which can be inefficient for large inputs.

  • May require two passes over the data in the worst case.

Solutions

class Solution {public  boolean doesValidArrayExist(int[] derived) {    int s = 0;    for (int x : derived) {      s ^= x;    }    return s == 0;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem