XOR Pairs less than K

JavaView on GFG

Intuition

Count pairs (i,j) where i<j and arr[i] XOR arr[j] < k. Trie-based counting.

Algorithm

1Build trie of binary representations. For each element: count previous elements with XOR < k using trie traversal.

Common Pitfalls

•Bit by bit trie traversal. At each bit: if k-bit is 1, count subtree with same bit (guaranteed < k), then go to opposite side.

XOR Pairs less than K.java

Java

// Approach: Sort array + Trie of binary representations. For each element, count pairs with XOR < K using Trie.
// Time: O(n * 32) Space: O(n * 32)
class Solution {
    class TrieNode {
        TrieNode[] child = new TrieNode[2];
        int count = 0;
    }

    private void insert(TrieNode root, int num) {
        TrieNode node = root;
        for (int i = 15; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.child[bit] == null)
                node.child[bit] = new TrieNode();
            node = node.child[bit];
            node.count++;
        }
    }

    private int query(TrieNode root, int num, int k) {
        TrieNode node = root;
        int res = 0;
        for (int i = 15; i >= 0 && node != null; i--) {
            int nBit = (num >> i) & 1;
            int kBit = (k >> i) & 1;
            if (kBit == 1) {
                if (node.child[nBit] != null)
                    res += node.child[nBit].count;
                node = node.child[nBit ^ 1];
            } else
                node = node.child[nBit];
        }
        return res;
    }

    public int cntPairs(int[] arr, int k) {
        TrieNode root = new TrieNode();
        int ans = 0;
        for (int num : arr) {
            ans += query(root, num, k);
            insert(root, num);
        }
        return ans;
    }
}

Was this solution helpful?