이웃 비트별 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(또한 길이 n)에서 인접한 값의 비트별 XOR(⊕)을 계산하여 생성된 길이 original의 0 인덱스 배열 n이 제공됩니다. 규칙은 다음과 같습니다.

• 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의 각 요소가 정확히 두 개의 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!