2425. Bitwise XOR of All Pairings

MediumView on LeetCode

Array Hash Table Bit Manipulation

Time: O(n)

Space: O(1)

Intuition

XOR of (nums1[i] XOR nums2[j]) for all pairs. Expand: XOR all values num1_i XOR num2_j. Count parity of occurrences.

Algorithm

1For each bit position b: count1 = bits set in nums1 at b, count0 = n - count1. count2_set in nums2.
2Pairs with bit set = count1*count2_set + count0*(n-count2_set). If odd: set bit in answer.

Common Pitfalls

•Process bit by bit. Bit b is set in XOR(all pairs) iff odd number of pairs have that bit set.

2425.cs

// Approach: Each nums1[i] appears |nums2| times; XOR result depends on parity of array sizes.
// Time: O(n) Space: O(1)

public class Solution
{
    public int XorAllNums(int[] nums1, int[] nums2)
    {
        // If the size of nums1 is m and the size of nums2 is n, then each number in
        // nums1 is repeated n times and each number in nums2 is repeated m times.
        int xors1 = nums1.Aggregate(0, (a, b) => a ^ b);
        int xors2 = nums2.Aggregate(0, (a, b) => a ^ b);
        return (nums1.Length % 2 * xors2) ^ (nums2.Length % 2 * xors1);
    }
}

Was this solution helpful?