Bitwise XOR of All Pairings

<?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. Bitwise XOR of All Pairings

Difficulty: Medium

Topics: Array, Bit Manipulation

Given two 0-indexed arrays, nums1 and nums2, containing non-negative integers. An array nums3 contains the bitwise XOR of all pairings between nums1 and nums2 (each integer in nums1 is paired with every integer in nums2 exactly once). Return the bitwise XOR of all integers in nums3.

Example 1:

• Input: nums1 = [2,1,3], nums2 = [10,2,5,0]
• Output: 13
• Explanation: A possible nums3 array is [8,0,7,2,11,3,4,1,9,1,6,3]. The bitwise XOR of all these numbers is 13.

Example 2:

• Input: nums1 = [1,2], nums2 = [3,4]
• Output: 0
• Explanation: Possible nums3 is [2,5,1,6]. 2 ^ 5 ^ 1 ^ 6 = 0.

Constraints:

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

Hint: Consider how the count of each individual integer affects the final answer. If nums1 has length m and nums2 has length n, each number in nums1 is repeated n times and each number in nums2 is repeated m times in the XOR sum.

Solution:

The key observation is that the XOR operation is associative and commutative. Also, x ^ x == 0. Therefore, if a number appears an even number of times in the XOR sum, it cancels itself out. We only need to consider numbers that appear an odd number of times.

Each number in nums1 appears n times in the XOR sum, and each number in nums2 appears m times. We can iterate through the bits of each number and count the total number of times each bit is set. If the total count of a bit is odd, it contributes to the final XOR result.

The provided PHP code efficiently implements this approach. The time complexity is O(m n) because we iterate through nums1 and nums2 once. The space complexity is O(1) because we use a constant amount of extra space.

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