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]:
i = n - 1, then derived[i] = original[i] ⊕ original[0].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.
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.length1 <= n <= 105derived are either 0's or 1'sIf there's a valid original array for a cycle, the sum of XOR results over the entire cycle must equal 0. Thus, you need to ensure the whole XOR sum of derived results in a consistent cycle.
Explanation: If you think about the cycle formed by the derived array indices, the conditions would imply that the XOR of all the derived elements should equal 0 in a valid binary sequence as every XOR pairs with its adjacent at least once in a valid set.
The solution iterates over the derived array and calculates the XOR sum of all the values. If the result is 0, it indicates a valid cycle exists for the binary array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in the derived array. We iterate through the array once.
Space Complexity: O(1), as we are only using a constant amount of extra space.
Attempt to reconstruct the original array by assuming initial possibilities and verify closure of cycle:
We shall try reconstructing the binary array by assuming the possible initial values (either 0 or 1) and iterating over each index to generate the subsequent value, checking if at the end, original[n] matches original[0] as intended.
We attempt possible reconstructions of the binary sequence starting with either 0 or 1. Using a helper function, we propagate potential values through original, verifying the closure for cycle integrity.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as two full passes of the derived array may be performed in the worst case.
Space Complexity: O(n), due to temporary storage needed for reconstruction.
| Approach | Complexity |
|---|---|
| Cycle Check via XOR Sum | Time Complexity: O(n), where n is the number of elements in the Space Complexity: O(1), as we are only using a constant amount of extra space. |
| Reconstruct and Verify | Time Complexity: O(n), as two full passes of the derived array may be performed in the worst case. Space Complexity: O(n), due to temporary storage needed for reconstruction. |
Neighboring Bitwise XOR - Leetcode 2683 - Python • NeetCodeIO • 6,381 views views
Watch 9 more video solutions →Practice Neighboring Bitwise XOR with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor