Bitwise XOR of All Pairings - Practice Coding Problems

Bitwise XOR of All Pairings - Problem

You are given two 0-indexed arrays, nums1 and nums2, consisting of non-negative integers.

Let there be another array, nums3, which contains the bitwise XOR of all pairings of integers between nums1 and nums2 (every integer in nums1 is paired with every integer in nums2 exactly once).

Return the bitwise XOR of all integers in nums3.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [2,1], nums2 = [3,4]

› Output: 2

💡 Note: All pairs: (2,3)→1, (2,4)→6, (1,3)→2, (1,4)→5. Final XOR: 1⊕6⊕2⊕5 = 2

Example 2 — Single Elements

$ Input: nums1 = [1], nums2 = [2]

› Output: 3

💡 Note: Only one pair: (1,2) → 1⊕2 = 3

Example 3 — Same Values

$ Input: nums1 = [1,2], nums2 = [3,4]

› Output: 0

💡 Note: Pairs: (1,3)→2, (1,4)→5, (2,3)→1, (2,4)→6. XOR: 2⊕5⊕1⊕6 = 0

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
0 ≤ nums1[i], nums2[j] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays nums1=[2,1] and nums2=[3,4]

Generate All Pairs

Create pairs: (2,3), (2,4), (1,3), (1,4) and XOR each

Final XOR

XOR all pair results: 1⊕6⊕2⊕5 = 2

Key Takeaway

🎯 Key Insight: XOR cancellation property allows us to avoid generating all pairs by analyzing element frequencies.

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that XOR has a cancellation property: elements that appear an even number of times cancel out. Each element in nums1 appears exactly len(nums2) times in all pairs, and vice versa. The optimal approach checks if these frequencies are odd and only XORs elements with odd frequencies. Best approach is XOR Properties with Time: O(n+m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - XOR Properties	O(n+m)	O(1)	Use XOR properties to avoid generating all pairs
Brute Force - Generate All Pairs	O(n×m)	O(1)	Generate all possible pairs and XOR them together

Optimized - XOR Properties — Algorithm Steps

Count how many times each element contributes to final result
If nums2 has odd length, XOR all nums1 elements
If nums1 has odd length, XOR all nums2 elements
Return the combined result

Visualization

Tap to expand

Step-by-Step Walkthrough

Frequency Count

Each nums1 element appears len(nums2) times in pairs

XOR Cancellation

Even occurrences cancel out, odd occurrences remain

Result

Only elements with odd frequency contribute

Code -

solution.c — C

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

int solution(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int result = 0;
    
    // If nums2 has odd length, each element in nums1 contributes to result
    if (nums2Size % 2 == 1) {
        for (int i = 0; i < nums1Size; i++) {
            result ^= nums1[i];
        }
    }
    
    // If nums1 has odd length, each element in nums2 contributes to result
    if (nums1Size % 2 == 1) {
        for (int i = 0; i < nums2Size; i++) {
            result ^= nums2[i];
        }
    }
    
    return result;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Remove newline
    line1[strcspn(line1, "\n")] = 0;
    line2[strcspn(line2, "\n")] = 0;
    
    int nums1[1000], nums2[1000];
    int nums1Size = 0, nums2Size = 0;
    
    // Parse first array
    char* token = strtok(line1 + 1, ",]");
    while (token != NULL) {
        nums1[nums1Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse second array
    token = strtok(line2 + 1, ",]");
    while (token != NULL) {
        nums2[nums2Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums1, nums1Size, nums2, nums2Size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n+m)

Single pass through nums1 (n elements) and nums2 (m elements)

✓ Linear Growth

Space Complexity

O(1)

Only using constant variables for accumulation

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 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

Optimized - XOR Properties — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler