Get started

Bitwise XOR of All Pairings — Medium Problem & Solution

Form every pair (nums1[i], nums2[j]) and XOR the two values. Collect all nums1.length * nums2.length results into a list.

Problem statement

Form every pair (nums1[i], nums2[j]) and XOR the two values. Collect all nums1.length * nums2.length results into a list.

Return the XOR of everything in that list.

Example 1

Input: nums1 = [2,1,3], nums2 = [10,2,5,0]
Output: 13
Explanation: Twelve pairings whose XORs cancel down to 13.

Example 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 0
Explanation: Both lengths are even, so everything cancels.

Example 3

Input: nums1 = [7], nums2 = [3,5]
Output: 6
Explanation: 7 XOR 3 = 4 and 7 XOR 5 = 2, and 4 XOR 2 = 6.

Constraints

  • 1 <= nums1.length, nums2.length <= 100000
  • 0 <= values <= 1000000000

How to solve Bitwise XOR of All Pairings

XOR is its own inverse, so a value that appears an even number of times contributes nothing. Each element of nums1 appears once per element of nums2, which reduces the whole computation to two parity checks.

Approach

  1. If nums2.length is odd, XOR every element of nums1 into the answer.
  2. If nums1.length is odd, XOR every element of nums2 into the answer.
  3. Return the accumulated value.

Why it works

nums1[i] occurs in exactly m = nums2.length pairings. XOR-ing it m times gives nums1[i] when m is odd and 0 when m is even, because x ^ x = 0. The same argument applies to nums2 with n = nums1.length.

Complexity

  • Time — O(n + m)
  • Space — O(1)

Pitfalls

  • Materialising the pairings is 10^10 operations at the stated limits.
  • Both conditions can hold at once — when both lengths are odd, both arrays contribute.
  • Neither holding is also fine; the answer is then 0.

Reference solution

Python

from typing import List

def xorAllNums(nums1: List[int], nums2: List[int]) -> int:
    out = 0
    if len(nums2) % 2 == 1:
        for x in nums1:
            out ^= x
    if len(nums1) % 2 == 1:
        for x in nums2:
            out ^= x
    return out

JavaScript

var xorAllNums = function(nums1, nums2) {
    var out = 0;
    if (nums2.length % 2 === 1) {
        for (var i = 0; i < nums1.length; i++) out ^= nums1[i];
    }
    if (nums1.length % 2 === 1) {
        for (var j = 0; j < nums2.length; j++) out ^= nums2[j];
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue