Find XOR Sum of All Pairs Bitwise AND

Hard
1324.

Find XOR Sum of All Pairs Bitwise AND

Find XOR Sum of All Pairs Bitwise AND is a hard coding problem on arrays, math and bit manipulation, asked in Amazon and Google interviews.

The XOR sum of a list is the bitwise XOR of all its elements (a one-element list's XOR sum is that element).

You are given two non-negative integer arrays arr1 and arr2. Form the list that holds arr1[i] AND arr2[j] for every pair (i, j) with 0 <= i < arr1.length and 0 <= j < arr2.length.

Return the XOR sum of that list.

Example 1

Input
arr1 = [3,5], arr2 = [6]
Output
6
Explanation
The list is `[3 AND 6, 5 AND 6] = [2,4]`, and `2 XOR 4 = 6`.

Example 2

Input
arr1 = [12], arr2 = [4]
Output
4

Example 3

Input
arr1 = [1,2,3], arr2 = [6,5]
Output
0
Explanation
The list is `[0,1,2,0,2,1]`; every value appears twice, so the XOR sum is 0.

Constraints

  • 1 <= arr1.length, arr2.length <= 10^5
  • 0 <= arr1[i], arr2[j] <= 10^9
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[]} arr1
 * @param {number[]} arr2
 * @return {number}
 */
var getXORSum = function(arr1, arr2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find XOR Sum of All Pairs Bitwise AND — Problem & Solution

Find XOR Sum of All Pairs Bitwise AND solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Find XOR Sum of All Pairs Bitwise AND is a hard coding problem on arrays, math and bit manipulation, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Math, Bit Manipulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The XOR sum of a list is the bitwise XOR of all its elements (a one-element list's XOR sum is that element).

You are given two non-negative integer arrays arr1 and arr2. Form the list that holds arr1[i] AND arr2[j] for every pair (i, j) with 0 <= i < arr1.length and 0 <= j < arr2.length.

Return the XOR sum of that list.

Example 1

Input: arr1 = [3,5], arr2 = [6]
Output: 6
Explanation: The list is `[3 AND 6, 5 AND 6] = [2,4]`, and `2 XOR 4 = 6`.

Example 2

Input: arr1 = [12], arr2 = [4]
Output: 4

Example 3

Input: arr1 = [1,2,3], arr2 = [6,5]
Output: 0
Explanation: The list is `[0,1,2,0,2,1]`; every value appears twice, so the XOR sum is 0.

Constraints

  • 1 <= arr1.length, arr2.length <= 10^5
  • 0 <= arr1[i], arr2[j] <= 10^9

Hints for Find XOR Sum of All Pairs Bitwise AND

  1. Hint 1

    There are up to 10^10 pairs, so the list can never be built.

  2. Hint 2

    Look at one bit position at a time: AND and XOR both work bit by bit.

  3. Hint 3

    AND distributes over XOR: (a1 AND b) XOR (a2 AND b) = (a1 XOR a2) AND b. Apply it to both arrays.

How to solve Find XOR Sum of All Pairs Bitwise AND

AND distributes over XOR exactly like multiplication over addition in arithmetic mod 2, so the XOR of all pairwise ANDs collapses to XOR(arr1) AND XOR(arr2).

Approach

  1. Compute x, the XOR of every element of arr1.
  2. Compute y, the XOR of every element of arr2.
  3. Return x AND y.

Why it works

Fix one bit. In that bit, AND is multiplication and XOR is addition modulo 2. The XOR over all pairs is then the sum over i and j of a_i * b_j mod 2, which factors as (sum of a_i) * (sum of b_j) mod 2 — the bit of XOR(arr1) times the bit of XOR(arr2). Every bit behaves independently, so the identity holds for whole numbers.

Complexity

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

Pitfalls

  • The double loop is correct but does up to 10^10 operations.
  • XOR the arrays first and AND once at the end — ANDing element by element and then XORing is a different expression.
  • The result is below 2^30, so no wide integers are needed.

Reference solution

Python

from typing import List

def getXORSum(arr1: List[int], arr2: List[int]) -> int:
    x = 0
    for v in arr1:
        x ^= v
    y = 0
    for v in arr2:
        y ^= v
    return x & y

Java

public static int getXORSum(int[] arr1, int[] arr2) {
    int x = 0, y = 0;
    for (int v : arr1) x ^= v;
    for (int v : arr2) y ^= v;
    return x & y;
}

C++

int getXORSum(vector<int>& arr1, vector<int>& arr2) {
    int x = 0, y = 0;
    for (int v : arr1) x ^= v;
    for (int v : arr2) y ^= v;
    return x & y;
}

JavaScript

var getXORSum = function(arr1, arr2) {
    var x = 0, y = 0;
    for (var i = 0; i < arr1.length; i++) x ^= arr1[i];
    for (var j = 0; j < arr2.length; j++) y ^= arr2[j];
    return x & y;
};

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