Bitwise XOR of All Pairings

Medium
722.

Bitwise XOR of All Pairings

Bitwise XOR of All Pairings is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var xorAllNums = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Bitwise XOR of All Pairings — Solution in Python, Java & C++

Bitwise XOR of All Pairings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Bitwise XOR of All Pairings is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Adobe interviews.

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

Hints for Bitwise XOR of All Pairings

  1. Hint 1

    Building the list is O(n·m) and far too slow. Count how many times each element is XOR-ed in.

  2. Hint 2

    nums1[i] appears in exactly nums2.length pairings, and XOR-ing a value an even number of times cancels it.

  3. Hint 3

    So nums1 contributes only when nums2.length is odd, and vice versa.

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

Java

public static int xorAllNums(int[] nums1, int[] nums2) {
    int out = 0;
    if (nums2.length % 2 == 1) {
        for (int x : nums1) out ^= x;
    }
    if (nums1.length % 2 == 1) {
        for (int x : nums2) out ^= x;
    }
    return out;
}

C++

int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
    int out = 0;
    if (nums2.size() % 2 == 1) {
        for (int x : nums1) out ^= x;
    }
    if (nums1.size() % 2 == 1) {
        for (int x : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation