すべてのペアリングのビットごとの 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

難易度: 中

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

非負の整数を含む 2 つの 0 インデックス配列 nums1 と nums2 を指定します。 配列 nums3 には、nums1 と nums2 の間のすべてのペアのビット単位の XOR が含まれます (nums1 の各整数は、nums2 のすべての整数と 1 回だけペアになります)。 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 を 1 回繰り返すため、時間計算量は O(m n) です。一定量の追加スペースを使用するため、スペースの複雑さは O(1) です。

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