2683: Neighboring-Bitwise-XOR
Medium
table of contents
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) {
^= derived[i];
prev }
return derived[derived.size()-1] == prev;
}
};