隣接するビットごとの 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. 隣接するビットごとの XOR

難易度: 中

トピック: 配列、ビット操作

長さ derived の 0 から始まる配列 n が与えられます。これは、バイナリ配列 original (これも長さ n) 内の隣接する値のビット単位の XOR (⊕) を計算することによって作成されます。 ルールは次のとおりです:

• i = n - 1の場合は、derived[i] = original[i] ⊕ original[0]。
• それ以外の場合は、derived[i] = original[i] ⊕ original[i 1].

私たちのタスクは、指定された original 配列を生成できる有効なバイナリ配列 derived が存在するかどうかを判断することです。 そのような配列が存在する場合は true を返し、存在しない場合は false を返します。 バイナリ配列には 0 と 1 のみが含まれます。

例 1:

• 入力: derived = [1,1,0]
• 出力: true
• 説明: 有効な original 配列は [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

例 2:

• 入力: derived = [1,1]
• 出力: true
• 説明: 有効な original 配列は [0,1].
です。

例 3:

• 入力: derived = [1,0]
• 出力: false
• 説明: 有効な original 配列が存在しません。

制約:

• n == derived.length
• 1 <= n <= 10^5
• derived の値は 0 または 1 です。

ヒント: derived 配列の XOR 合計は 0 である必要があります。

解決策 (PHP):

重要な観察は、有効な derived 配列が存在する場合、original 配列の XOR 合計は常に 0 になるということです。 これは、original の各要素が 2 つの XOR 演算に関与しているためです (最初と最後の要素が XOR 演算されるエッジケースを除きますが、その場合でもキャンセルされます)。

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

?>この解の時間計算量は O(n)、空間計算量は O(1) です。  再構築することなく、有効な 
 配列の存在を効率的に判断します。original

以上が隣接するビットごとの XORの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。