XOR au niveau du bit voisin

<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. XOR au niveau du bit voisin

Difficulté :Moyen

Sujets : Tableau, manipulation de bits

Nous recevons un tableau indexé 0 derived de longueur n, créé en calculant le XOR au niveau du bit (⊕) des valeurs adjacentes dans un tableau binaire original (également de longueur n). La règle est la suivante :

• Si i = n - 1, alors derived[i] = original[i] ⊕ original[0].
• Sinon, derived[i] = original[i] ⊕ original[i 1].

Notre tâche est de déterminer s'il existe un tableau binaire valide original qui pourrait produire le tableau derived donné. Renvoie true si un tel tableau existe, false sinon. Un tableau binaire ne contient que des 0 et des 1.

Exemple 1 :

• Entrée : derived = [1,1,0]
• Sortie : true
• Explication : Un tableau original valide est [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

Exemple 2 :

• Entrée : derived = [1,1]
• Sortie : true
• Explication : Un tableau original valide est [0,1].

Exemple 3 :

• Entrée : derived = [1,0]
• Sortie : false
• Explication : Aucun tableau original valide n'existe.

Contraintes :

• n == derived.length
• 1 <= n <= 10^5
• Les valeurs dans derived sont soit des 0, soit des 1.

Indice : La somme XOR du derived tableau doit être 0.

Solution (PHP) :

L'observation clé est que la somme XOR du tableau derived sera toujours 0 si un tableau original valide existe. En effet, chaque élément de original est impliqué dans exactement deux opérations XOR (sauf dans les cas extrêmes où le premier et le dernier élément sont XOR, mais même dans ce cas, cela s'annule).

<?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

?>
Cette solution a une complexité temporelle de O(n) et une complexité spatiale de O(1).  Il détermine efficacement l'existence d'un original tableau valide sans avoir besoin de le reconstruire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!