모든 쌍의 비트별 XOR

<?php
function xorAllPairings($nums1, $nums2) {
    $m = count($nums1);
    $n = count($nums2);
    $result = 0;

    for ($i = 0; $i < 32; $i++) {
        $count1 = 0;
        $count2 = 0;

        foreach ($nums1 as $num) {
            if (($num >> $i) & 1) {
                $count1++;
            }
        }

        foreach ($nums2 as $num) {
            if (($num >> $i) & 1) {
                $count2++;
            }
        }

        $totalCount = $count1 * $n + $count2 * $m;
        if ($totalCount % 2 != 0) {
            $result |= (1 << $i);
        }
    }

    return $result;
}

// Example 1
$nums1 = [2, 1, 3];
$nums2 = [10, 2, 5, 0];
echo xorAllPairings($nums1, $nums2); // Output: 13

// Example 2
$nums1 = [1, 2];
$nums2 = [3, 4];
echo xorAllPairings($nums1, $nums2); // Output: 0
?>

2425. 모든 쌍의 비트별 XOR

난이도:중

주제: 어레이, 비트 조작

음수가 아닌 정수를 포함하는 두 개의 0 인덱스 배열 nums1 및 nums2이 제공됩니다. 배열 nums3에는 nums1과 nums2 사이의 모든 쌍에 대한 비트별 XOR이 포함됩니다(nums1의 각 정수는 nums2의 모든 정수와 정확히 한 번 쌍을 이룹니다). nums3에 있는 모든 정수의 비트별 XOR을 반환합니다.

예 1:

• 입력: nums1 = [2,1,3], nums2 = [10,2,5,0]
• 출력: 13
• 설명: 가능한 nums3 배열은 [8,0,7,2,11,3,4,1,9,1,6,3]입니다. 이 모든 숫자의 비트별 XOR은 13입니다.

예 2:

• 입력: nums1 = [1,2], nums2 = [3,4]
• 출력: 0
• 설명: 가능한 nums3은 [2,5,1,6]입니다. 2^5^1^6 = 0.

제약조건:

• 1 ≤ nums1.length, nums2.length ≤ 10⁵
• 0 ≤ nums1[i], nums2[i] ≤ 10⁹

힌트: 각 정수의 개수가 최종 답변에 어떤 영향을 미치는지 생각해 보세요. nums1의 길이가 m이고 nums2의 길이가 n인 경우 nums1의 각 숫자는 n회 반복되고 nums2의 각 숫자는 XOR 합계에서 m회 반복됩니다.

해결책:

주요 관찰은 XOR 연산이 결합적이고 교환적이라는 것입니다. 또, x ^ x == 0. 따라서 숫자가 XOR 합계에서 짝수 번 나타나면 자체적으로 취소됩니다. 홀수 번 나타나는 숫자만 고려하면 됩니다.

nums1의 각 숫자는 XOR 합계에서 n회 나타나고, nums2의 각 숫자는 m회 나타납니다. 각 숫자의 비트를 반복하여 각 비트가 설정된 총 횟수를 계산할 수 있습니다. 비트의 총 개수가 홀수이면 최종 XOR 결과에 기여합니다.

제공된 PHP 코드는 이 접근 방식을 효율적으로 구현합니다. nums1과 nums2을 한 번 반복하므로 시간 복잡도는 O(m n)입니다. 일정한 양의 추가 공간을 사용하므로 공간 복잡도는 O(1)입니다.

위 내용은 모든 쌍의 비트별 XOR의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!