Introduction

The problem is to find the number of pairs (i, j) in an array such that the bitwise XOR of the pair is less than a given integer k.

For example, given the array [1, 2, 3, 5] and k = 5, the valid pairs are:

Thus, the output is 4.

Understanding XOR and Pairs

The bitwise XOR operator (^) compares two numbers bit by bit. The XOR of two numbers is less than k if their binary representation results in a number smaller than the binary representation of k.

A brute-force solution would check all possible pairs:

for i = 0 to n-1:
    for j = i+1 to n-1:
        if (arr[i] ^ arr[j]) < k:
            count++

This works in O(n²) time, but for large arrays (n up to 5 * 10⁴), this is too slow.

Optimized Approach Using Trie

We can optimize using a Trie (prefix tree) built for binary representations of numbers.

Key Idea

How Counting Works

Consider a number num and k in binary.

We traverse the Trie from the most significant bit (MSB) to the least significant bit (LSB).

At each bit:

This ensures we count only those numbers whose XOR with num is less than k.

Java Solution

class Solution {

    static class TrieNode {
        TrieNode[] child = new TrieNode[2];
        int count = 0; // Count of numbers passing through this node
    }

    public int cntPairs(int[] arr, int k) {
        TrieNode root = new TrieNode();
        int count = 0;

        for (int num : arr) {
            count += countLessXOR(root, num, k, 15); // max 15 bits because arr[i] <= 5*10^4
            insert(root, num, 15);
        }

        return count;
    }

    private void insert(TrieNode root, int num, int bit) {
        TrieNode node = root;

        for (int i = bit; i >= 0; i--) {
            int b = (num >> i) & 1;
            if (node.child[b] == null) {
                node.child[b] = new TrieNode();
            }
            node = node.child[b];
            node.count++;
        }
    }

    private int countLessXOR(TrieNode root, int num, int k, int bit) {
        TrieNode node = root;
        int count = 0;

        for (int i = bit; i >= 0 && node != null; i--) {
            int bNum = (num >> i) & 1;
            int bK = (k >> i) & 1;

            if (bK == 1) {
                // Add count of numbers with same bit as bNum
                if (node.child[bNum] != null) {
                    count += node.child[bNum].count;
                }
                node = node.child[1 - bNum]; // Move to opposite branch
            } else {
                node = node.child[bNum]; // Only same bit branch allowed
            }
        }

        return count;
    }
}

Example Run

Input

arr = [1, 2, 3, 5], k = 5

Step-by-Step

Final answer = 4

Complexity Analysis

Time Complexity

O(n * log(max(arr[i])))

Since numbers are bounded by 5 * 10⁴ and:

log2(5 * 10^4) ≈ 16

the complexity is effectively O(n).

Space Complexity

O(n * log(max(arr[i])))

This space is used for storing Trie nodes.

Key Insight

Trie helps efficiently count numbers whose XOR with a given number is less than k. Instead of checking all possible pairs, we navigate the binary bits of the numbers and k to prune impossible options. This reduces the complexity dramatically from O(n²) to nearly O(n) and makes the solution practical for large input sizes.

Summary

To count pairs whose XOR is less than a given value k, a brute-force approach becomes inefficient for large arrays because it requires checking every pair. A Trie-based solution stores binary representations of previously seen numbers and efficiently counts valid XOR combinations bit by bit. By leveraging the binary properties of XOR and the structure of a Trie, the algorithm reduces the time complexity from O(n²) to approximately O(n), making it suitable for arrays containing tens of thousands of elements.