Count pairs having Bitwise XOR less than K

Given an array arr[] and an integer k, Find the number of pairs (i, j) with i < j such that arr[i] XOR arr[j] is less than k. Each valid pair is counted only once.

Examples:

Input: arr = [1, 2, 3, 5], k = 5
Output: 4
Explanation: Bitwise XOR of all possible pairs that satisfy the given conditions are:
arr[0] ^ arr[1] = 1 ^ 2 = 3
arr[0] ^ arr[2] = 1 ^ 3 = 2
arr[0] ^ arr[3] = 1 ^ 5 = 4
arr[1] ^ arr[2] = 2 ^ 3 = 1
Therefore, the required output is 4.
Input: arr[] = [3, 5, 6, 8], k = 7
Output: 3
Explanation: Bitwise XOR of all possible pairs that satisfy the given conditions are:
arr[0] ^ arr[1] = 6
arr[0] ^ arr[2] = 5
arr[1] ^ arr[2] = 3
Therefore, the required output is 3.

Try it on GfG Practice

Table of Content

[Naive Approach] By generating all pairs - O(n^2) Time and O(1) Space
[Expected Approach] Using Trie

[Naive Approach] By generating all pairs - O(n²) Time and O(1) Space

The approach to solve this problem is to traverse the given array and generate all possible pairs of the given array and for each pair, check if bitwise XOR of the pair is less than k or not. If found to be true, then increment the count of pairs having bitwise XOR less than k.

C++

//Driver Code Starts
#include <iostream>
#include<vector>
using namespace std;

//Driver Code Ends

int cntPairs(vector<int>&arr, int k) {
    int n=arr.size();
    int cnt = 0;
    
    // Loop through all possible pairs of elements in the array
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            
            // Check if bitwise XOR of the pair is less than K
            if ((arr[i] ^ arr[j]) < k) {
                cnt++;
            }
        }
    }
    
    // return all pairs less than k
    return cnt;
}

//Driver Code Starts

int main()
{
    vector<int>arr= {3, 5, 6, 8};
    int k= 7;
    cout<<cntPairs(arr,k)<<endl;
}

//Driver Code Ends

Java

//Driver Code Starts
class GFG {

//Driver Code Ends

    static int cntPairs(int[] arr, int k) {
        int n = arr.length;
        int cnt = 0;

        // Loop through all possible pairs of elements in the array
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {

                // Check if bitwise XOR of the pair is less than K
                if ( (arr[i] ^ arr[j]) < k ) {
                    cnt++;
                }
            }
        }

        // return all pairs less than k
        return cnt;
    }

//Driver Code Starts

    public static void main(String[] args) {
        int[] arr = {3, 5, 6, 8};
        int k = 7;
        System.out.println(cntPairs(arr, k));
    }
}

//Driver Code Ends

Python

def cntPairs(arr, k):
    n = len(arr)
    cnt = 0

    # Loop through all possible pairs of elements in the array
    for i in range(n):
        for j in range(i + 1, n):

            # Check if bitwise XOR of the pair is less than K
            if (arr[i] ^ arr[j]) < k:
                cnt += 1

    # return all pairs less than k
    return cnt


#Driver Code Starts

if __name__ == '__main__':
    arr = [3, 5, 6, 8]
    k = 7
    print(cntPairs(arr, k))

#Driver Code Ends

//Driver Code Starts
using System;

class GFG {
//Driver Code Ends


    static int cntPairs(int[] arr, int k) {
        int n = arr.Length;
        int cnt = 0;

        // Loop through all possible pairs of elements in the array
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {

                // Check if bitwise XOR of the pair is less than K
                if ((arr[i] ^ arr[j]) < k) {
                    cnt++;
                }
            }
        }

        // return all pairs less than k
        return cnt;
    }

//Driver Code Starts

    static void Main() {
        int[] arr = {3, 5, 6, 8};
        int k = 7;
        Console.WriteLine(cntPairs(arr, k));
    }
}

//Driver Code Ends

JavaScript

function cntPairs(arr, k) {
    let n = arr.length;
    let cnt = 0;

    // Loop through all possible pairs of elements in the array
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {

            // Check if bitwise XOR of the pair is less than K
            if ((arr[i] ^ arr[j]) < k) {
                cnt++;
            }
        }
    }

    // return all pairs less than k
    return cnt;
}


//Driver Code Starts
// Driver Code
let arr = [3, 5, 6, 8];
let k = 7;
console.log(cntPairs(arr, k));

//Driver Code Ends

Output

[Expected Approach] Using Trie

Instead of explicitly forming all pairs, we insert numbers one by one into the Trie. For every new number x, before inserting it, we ask the Trie: “How many numbers inserted so far have their XOR with x less than k?”
So the Trie helps us count valid pairs without checking every combination.

How Trie Works for XOR < k?
We compare numbers bit by bit (from the most significant bit to the least). At each bit position, we look at: Bit of the current number (x) and Bit of k. Depending on the bit of k, two situations arise:

Case 1: Bit of k is 1, it means:
Numbers whose XOR with x at this bit becomes 0 still keep the total value < K. So all numbers that match the same bit as x can be counted immediately. After counting them, we can still explore numbers that differ from x at that bit, because XOR at this bit becomes 1 (which matches k) - so we need to continue checking remaining bits.
Case 2: Bit of k is 0, It means:
XOR at this bit must also be 0 to stay below k. So the only valid option is to follow the same bit as x. If a different bit is taken, XOR becomes 1 - which already exceeds k at this bit so that path is not allowed.

After completing the entire process - querying the Trie for every element and then inserting it - we will have the total count of all valid pairs whose XOR is less than k.

C++

//Driver Code Starts
#include <iostream> 
#include<vector>
using namespace std; 
//Driver Code Ends


class TrieNode 
{ 
    public:
    
    // Stores binary representation 
    // of numbers 
    TrieNode *child[2]; 

    // Stores count of elements 
    // present in a node 
    int cnt; 
    TrieNode() { 
        child[0] = child[1] = NULL; 
        cnt = 0; 
    } 
}; 


// Function to insert a number into Trie 
void insertTrie(TrieNode *root, int n) { 
    
    // Traverse binary representation of x 
    for (int i = 31; i >= 0; i--) { 
        
        // Stores ith bit of n 
        bool x = (n) & (1 << i); 
        
        // Check if an element already 
        // present in Trie having ith bit x
        if(!root->child[x]) { 
            root->child[x] = new TrieNode(); 
        } 
        
        // Update count of elements 
        // whose ith bit is x 
        root->child[x]->cnt+= 1; 
        
        // Update root 
        root= root->child[x]; 
    } 
} 


// Function to count elements 
// in Trie whose XOR with n 
// less than k
int cntSmaller(TrieNode * root, 
                int n, int k) 
{
    int cntPairs = 0; 
    
    // Traverse binary representation 
    // of n and k in Trie 
    for (int i = 31; i >= 0 && 
                    root; i--) { 
                                    
        // Stores ith bit of n                         
        bool x = n & (1 << i); 
        
        // Stores ith bit of k
        bool y = k & (1 << i); 
        
        // If the ith bit of k is 1 
        if (y) { 
            
            // If an element already 
            // present in Trie having 
            // ith bit (x)
            if(root->child[x]) {
                    cntPairs  +=
                    root->child[x]->cnt; 
            }
        
            root = 
                root->child[1 - x]; 
        } 
        
        // If the ith bit of k is 0 
        else{ 
            
            // Update root 
            root = root->child[x]; 
        } 
    } 
    return cntPairs; 
} 

// Function to count pairs that 
// satisfy the given conditions
int cntPairs(vector<int>&arr,int k) { 
    
    // Create root node of Trie 
    TrieNode *root = new TrieNode(); 

    int cntPairs = 0; 
    int n=arr.size();
    
    // Traverse the given array 
    for(int i = 0;i < n; i++){ 
        
        // Update cntPairs 
        cntPairs += cntSmaller(root, 
                        arr[i], k); 
        
        // Insert arr[i] into Trie 
        insertTrie(root, arr[i]); 
    } 
    return cntPairs; 
} 

//Driver Code Starts

int main() 
{ 
    vector<int>arr= {3, 5, 6, 8}; 
    int k= 7; 
    cout<<cntPairs(arr,k); 
} 


//Driver Code Ends