XOR Over All Pairwise ANDs

Hard

You are given two arrays of non-negative integers, first and second. For every pair (i, j), where i indexes first and j indexes second, compute first[i] AND second[j] (bitwise AND). That gives len(first) · len(second) numbers. Return the bitwise XOR of all of them. With lengths up to 10⁵, going through every pair is too slow, so look for a faster way.

Example 1

first=[5, 3], second=[6] → 6

5 AND 6 = 4 and 3 AND 6 = 2, and 4 XOR 2 = 6.

Example 2

first=[7], second=[1, 2, 4] → 7

The pairs give 1, 2 and 4; 1 XOR 2 XOR 4 = 7.

Example 3

first=[8, 8], second=[15] → 0

Both pairs give 8, and 8 XOR 8 = 0.

Constraints

1 ≤ len(first), len(second) ≤ 10⁵
0 ≤ first[i], second[j] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Math

Similar problems

Checkerboard by Swapping Lines Hard Two Groups With the Same Average Hard XOR Tile Duel Hard Square-Sum Chains Hard Product of Distinct Primes Hard

Input

first=[5, 3], second=[6]

Expected

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.