Q: Count array pairs with bitwise AND > k ~ better than O(N^2) possible?

Question

Given an array nums

Count no. of pairs (two elements) where bitwise AND is greater than K

Brute force

for i in range(0,n):
   for j in range(i+1,n):
       if a[i]&a[j] > k:
           res += 1

Better version: preprocess to remove all elements ≤k and then brute force

But i was wondering, what would be the limit in complexity here?

Can we do better with a trie, hashmap approach like two-sum?

( I did not find this problem on Leetcode so I thought of asking here )

Answer 1

Let size_of_input_array = N. Let the input array be of B-bit numbers

Here is an easy to understand and implement solution.

• Eliminate all values <= k.

• The above image shows 5 10-bit numbers.

Step 1: Adjacency Graph

• Store a list of set bits. In our example, 7th bit is set for numbers at index 0,1,2,3 in the input array.

Step 2: The challenge is to avoid counting the same pairs again.

To solve this challenge we take help of union-find data structure as shown in the code below.

//unordered_map<int, vector<int>> adjacency_graph;
//adjacency_graph has been filled up in step 1

vector<int> parent;
for(int i = 0; i < input_array.size(); i++)
    parent.push_back(i);

int result = 0;
for(int i = 0; i < adjacency_graph.size(); i++){ // loop 1
    auto v = adjacency_graph[i];
    if(v.size() > 1){
        int different_parents = 1;
        for (int j = 1; j < v.size(); j++) { // loop 2
            int x = find(parent, v[j]);
            int y = find(parent, v[j - 1]);
            if (x != y) {
                different_parents++;
                union(parent, x, y);
            }
        }
        result += (different_parents * (different_parents - 1)) / 2;
    }
}
return result;

In the above code, find and union are from union-find data structure.

Time Complexity:

Step 1:

Build Adjacency Graph: O(BN)

Step 2:

Loop 1: O(B)
Loop 2: O(N * Inverse of Ackermann’s function which is an extremely slow-growing function) 

Overall Time Complexity

= O(BN)

Space Complexity

Overall space complexity = O(BN)

Answer 2

First, prune everything <= k. Also Sort the value list.

Going from the most significant bit to the least significant we are going to keep track of the set of numbers we are working with (initially all ,s=0, e=n).

Let p be the first position that contains a 1 in the current set at the current position.

If the bit in k is 0, then everything that would yield a 1 world definetly be good and we need to investigate the ones that get a 0. We have (end - p) * (end-p-1) /2 pairs in the current range and (end-p) * <total 1s in this position larger or equal to end> combinations with larger previously good numbers, that we can add to the solution. To continue we update end = p. We want to count 1s in all the numbers above, because we only counted them before in pairs with each other, not with the numbers this low in the set.

If the bit in k is 1, then we can't count any wins yet, but we need to eliminate everything below p, so we update start = p.

You can stop once you went through all the bits or start==end.

Details:

• Since at each step we eliminate either everything that has a 0 or everything that has a 1, then everything between start and end will have the same bit-prefix. since the values are sorted we can do a binary search to find p.
• For <total 1s in this position larger than p>. We already have the values sorted. So we can compute partial sums and store for every position in the sorted list the number of 1s in every bit position for all numbers above it.

Complexity:

• We got bit-by-bit so L (the bit length of the numbers), we do a binary search (logN), and lookup and updates O(1), so this is O(L logN).
• We have to sort O(NlogN).
• We have to compute partial bit-wise sums O(L*N).

Total O(L logN + NlogN + L*N).

Since N>>L, L logN is subsummed by NlogN. Since L>>logN (probably, as in you have 32 bit numbers but you don't have 4Billion of them), then NlogN is subsummed by L*N. So complexity is O(L * N). Since we also need to keep the partial sums around the memory complexity is also O(L * N).