Sum of XOR of all pairs

Intuition

XOR of two numbers at bit position i equals 1 only when the two numbers differ at that bit. So instead of checking every pair, count for each bit how many numbers have it set (count1) and how many do not (count0). Every one of the count1 × count0 pairs contributes 2^i to the total XOR sum.

Algorithm

1Initialise total = 0.
2For each bit position i from 0 to 31:
3 Count count1 = number of elements in arr with bit i set.
4 count0 = n − count1.
5 total += count1 * count0 * (1L << i).
6Return total.

Example Walkthrough

Input: arr = [1, 2, 3]

1.Bit 0 (value 1): set in 1,3 → count1=2, count0=1 → contribution = 2×1×1 = 2.
2.Bit 1 (value 2): set in 2,3 → count1=2, count0=1 → contribution = 2×1×2 = 4.
3.All higher bits: count1=0 → contribution = 0.
4.Total = 2 + 4 = 6.
5.Verify: XOR(1,2)=3, XOR(1,3)=2, XOR(2,3)=1 → sum = 6. ✓

Output: 6

Common Pitfalls

•Use 1L << i (long shift) to avoid int overflow for bit positions ≥ 31.
•Multiply count1 * count0 as long before multiplying by the bit value to prevent overflow.
•Each unordered pair is counted exactly once because count1 × count0 counts one element from each group per pair.

Sum of XOR of all pairs.java

Java


// Approach: For each bit position i, a pair contributes 2^i to the XOR sum only when exactly
// one of the two numbers has that bit set. If count1 numbers have bit i set and count0 = n - count1
// do not, then count1 * count0 pairs each contribute 2^i. Summing over all 32 bit positions gives
// the total XOR sum across all unordered pairs in O(32 * N) = O(N) time.
//
// Time: O(N) — 32 passes of length N.
// Space: O(1) — only a counter per bit position.
class Solution {

    public long sumXOR(int[] arr) {
        int n = arr.length;
        long total = 0;
        // Check each bit position (0–31)
        for (int i = 0; i < 32; i++) {
            long count1 = 0;
            for (int num : arr) {
                if ((num & (1 << i)) != 0) {
                    count1++;
                }
            }
            
            long count0 = n - count1;
            total += count1 * count0 * (1L << i);
        }

        return total;
    }
}

Was this solution helpful?