Neighboring Bitwise XOR

<code class="language-php"><?php
/**
 * @param Integer[] $derived
 * @return Boolean
 */
function doesValidArrayExist($derived) {
    $xorSum = 0;
    foreach ($derived as $num) {
        $xorSum ^= $num;
    }
    return $xorSum === 0;
}

// Example 1
$derived1 = [1, 1, 0];
echo doesValidArrayExist($derived1) ? 'true' : 'false'; // Output: true

// Example 2
$derived2 = [1, 1];
echo doesValidArrayExist($derived2) ? 'true' : 'false'; // Output: true

// Example 3
$derived3 = [1, 0];
echo doesValidArrayExist($derived3) ? 'true' : 'false'; // Output: false
?></code>

2683. Neighboring Bitwise XOR

Difficulty: Medium

Topics: Array, Bit Manipulation

We're given a 0-indexed array derived of length n, created by computing the bitwise XOR (⊕) of adjacent values in a binary array original (also of length n). The rule is:

• If i = n - 1, then derived[i] = original[i] ⊕ original[0].
• Otherwise, derived[i] = original[i] ⊕ original[i 1].

Our task is to determine if a valid binary array original exists that could produce the given derived array. Return true if such an array exists, false otherwise. A binary array contains only 0s and 1s.

Example 1:

• Input: derived = [1,1,0]
• Output: true
• Explanation: A valid original array 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 is [0,1].

Example 3:

• Input: derived = [1,0]
• Output: false
• Explanation: No valid original array exists.

Constraints:

• n == derived.length
• 1 <= n <= 10^5
• The values in derived are either 0s or 1s.

Hint: The XOR sum of the derived array should be 0.

Solution (PHP):

The key observation is that the XOR sum of the derived array will always be 0 if a valid original array exists. This is because each element of original is involved in exactly two XOR operations (except in edge cases where the first and last elements are XORed, but even then it cancels out).

<?php
function doesValidArrayExist(array $derived): bool {
    $xorSum = 0;
    foreach ($derived as $val) {
        $xorSum ^= $val;
    }
    return $xorSum === 0;
}

// Test cases
$derived1 = [1, 1, 0];
echo doesValidArrayExist($derived1) ? "true\n" : "false\n"; // true

$derived2 = [1, 1];
echo doesValidArrayExist($derived2) ? "true\n" : "false\n"; // true

$derived3 = [1, 0];
echo doesValidArrayExist($derived3) ? "true\n" : "false\n"; // false

$derived4 = [1,0,1,0,1];
echo doesValidArrayExist($derived4) ? "true\n" : "false\n"; //true

$derived5 = [1,0,1,0,0];
echo doesValidArrayExist($derived5) ? "true\n" : "false\n"; //false

?>
This solution has a time complexity of O(n) and a space complexity of O(1).  It efficiently determines the existence of a valid original array without needing to reconstruct it.

The above is the detailed content of Neighboring Bitwise XOR. For more information, please follow other related articles on the PHP Chinese website!