Find XOR Sum of All Pairs Bitwise AND - Practice Coding Problems

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

Understanding the Visualization

Input Arrays

Two arrays arr1=[1,2] and arr2=[3,4,5]

Generate AND Pairs

Compute arr1[i] & arr2[j] for all i,j combinations

XOR Sum

XOR all AND results: 1⊕0⊕1⊕2⊕0⊕0 = 2

Key Takeaway

🎯 Key Insight: Generate all possible AND pairs between arrays, then XOR all results together

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

Approach	Time	Space	Notes
✓ Brute Force - Generate All Pairs	O(n×m)	O(n×m)	Generate all possible AND pairs, then compute XOR sum
Mathematical Pattern Recognition	O(n×m)	O(1)	Use XOR distributive property to compute result bit by bit
Bit Manipulation Optimization	O(n×m)	O(1)	Compute XOR sum directly without storing intermediate results

Brute Force - Generate All Pairs — Algorithm Steps

Generate all arr1[i] AND arr2[j] pairs
Store all AND results in a list
Compute XOR sum of the list

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Pairs

Create arr1[i] & arr2[j] for all i,j

Store Results

Collect all AND results in a list

XOR Sum

Compute XOR of all collected results

Code -

solution.c — C

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

int solution(int* arr1, int arr1Size, int* arr2, int arr2Size) {
    int* pairs = malloc(arr1Size * arr2Size * sizeof(int));
    int pairCount = 0;
    
    for (int i = 0; i < arr1Size; i++) {
        for (int j = 0; j < arr2Size; j++) {
            pairs[pairCount++] = arr1[i] & arr2[j];
        }
    }
    
    int result = 0;
    for (int i = 0; i < pairCount; i++) {
        result ^= pairs[i];
    }
    
    free(pairs);
    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)

Nested loops generate n×m pairs, each AND operation is O(1)

✓ Linear Growth

Space Complexity

O(n×m)

Store all n×m AND results in a list before computing XOR

⚡ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler