Find XOR Sum of All Pairs Bitwise AND - Problem

The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element.

For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4, and the XOR sum of [3] is equal to 3.

You are given two 0-indexed arrays arr1 and arr2 that consist only of non-negative integers.

Consider the list containing the result of arr1[i] AND arr2[j] (bitwise AND) for every (i, j) pair where 0 <= i < arr1.length and 0 <= j < arr2.length.

Return the XOR sum of the aforementioned list.

Input & Output

Example 1 — Basic Case

$ Input: arr1 = [1,2], arr2 = [3,4,5]

› Output: 2

💡 Note: All pairs: (1&3)=1, (1&4)=0, (1&5)=1, (2&3)=2, (2&4)=0, (2&5)=0. XOR sum: 1⊕0⊕1⊕2⊕0⊕0 = 2

Example 2 — Single Elements

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

› Output: 4

💡 Note: Only one pair: 12 & 4 = 4. XOR sum of [4] = 4

Example 3 — All Zero Results

$ Input: arr1 = [1], arr2 = [2,4]

› Output: 0

💡 Note: Pairs: (1&2)=0, (1&4)=0. XOR sum: 0⊕0 = 0

Constraints

1 ≤ arr1.length, arr2.length ≤ 10⁵
0 ≤ arr1[i], arr2[j] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 F Facebook 12 A Amazon 8 M Microsoft 6

This problem requires computing the XOR sum of all possible bitwise AND pairs between two arrays. The key insight is that we can compute the XOR directly without storing intermediate results. The most straightforward approach uses nested loops with O(n×m) time and O(1) space. Advanced approaches can analyze bit patterns, but the core complexity remains the same. Best approach: Direct XOR computation. Time: O(n×m), Space: O(1)

Common Approaches

✓ Bit Manipulation Optimization

⏱️ Time: O(n×m) Space: O(1)

Instead of storing all AND results, compute the XOR sum on-the-fly. This reduces space complexity while maintaining the same time complexity for generating pairs.

Brute Force - Generate All Pairs

⏱️ Time: O(n×m) Space: O(n×m)

For each element in arr1, compute AND with each element in arr2, store results in a list, then compute XOR of all results. This directly follows the problem definition.

Mathematical Pattern Recognition

⏱️ Time: O(n×m) Space: O(1)

Apply the mathematical insight that XOR is distributive. We can analyze each bit position separately across all numbers and use properties of XOR to compute the result more efficiently.

Bit Manipulation Optimization — Algorithm Steps

Initialize result as 0
For each pair (i,j), compute arr1[i] & arr2[j]
XOR the result with running total

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with result = 0

Compute & XOR

For each pair, compute AND and XOR with result

Final Result

Return accumulated XOR value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr1, int arr1Size, int* arr2, int arr2Size) {
    int result = 0;
    for (int i = 0; i < arr1Size; i++) {
        for (int j = 0; j < arr2Size; j++) {
            result ^= (arr1[i] & arr2[j]);
        }
    }
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr1[100], arr1Size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            arr1[arr1Size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    int arr2[100], arr2Size = 0;
    token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            arr2[arr2Size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(arr1, arr1Size, arr2, arr2Size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Still need to generate all n×m pairs with nested loops

✓ Linear Growth

Space Complexity

O(1)

Only use constant extra space for the running XOR result

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Find XOR Sum of All Pairs Bitwise AND - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler