Lakh's blog

Count pairs in an array with xor less than K
By Lakh, history, 6 years ago, In English

Given an array of N elements count no. of pairs having XOR less than K. How to solve this problem??

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can do it with Walsh-Hadamard transform.

→ Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Building a trie may solve this problems. You should implement two main functions: add a number x into trie and count number of value in trie which XOR with x having result less then K.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

It can be solved using trie see the link for details

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a pretty common trie problem.

Suppose your array is A B C D E F.

What can we do if we want to find number of pairs whose one element is E, and the other is some element in left of E?

Let's assume a pair is (X, E) such that X^E < K.

Now, let's say the binary of K is 11010. E is 01010.

So, what can the leftmost bit of X be? If it's 1, the leftmost bit of (B xor E) will be 1, which is equal to K's leftmost bit. So, it must be 0.

At this point, let's do some more works first. Before finding how many pairs E has, insert all elements in left of it in a trie, so you have inserted A B C D at this point.

Now, we wanted to find a number among these whose leftmost bit is 0, so that when xor'ed with E, the resultant's leftmost bit will be smaller than K's leftmost bit. So, from root of trie, you check if you can go to a node with 0. If you can't, it means no pair exists for E.

After that, we can do the same thing for the next bit. The next bit of E is 1. Next bit of K is also 1. So X must have 1 bit in this position. So, this time, from current node of trie, you trie to get to a node with 1.

This is the basic of such problems. I suggest you to get familiar with trie and solve its straightforward problems first if you haven't already. Then brainstorm with these basics and try to solve this one.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you went wrong here Now, we wanted to find a number among these whose leftmost bit is 0, so that when xor'ed with E, the resultant's leftmost bit will be smaller than K's leftmost bit. So, from root of trie, you check if you can go to a node with 0. If you can't, it means no pair exists for E.

    If we do not find a number whose leftmost bit xored with E's leftmost bit isn't less than the left most bit of X but this xor is equal to the left most bit of K), then we still find a number in the trie which xors with E to be less than K. No pair exist only if the resultant xor becomes > the corresponding bit at K.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. By "If you can't, it means no pair exists for E.", I actually wanted to say "If you can't, it means no pair exists for E where leftmost bit is smaller."

      After that, you need to go on and try that for the next bit (which makes it equal up to the previous bit)

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to find solution for each value of x from 0<=x<=k.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      For each node that guarantees x < k, you add count of all numbers under that node, i.e. all x that goes through that node. Then, you traverse to the other node and go one level below (next bit position).

      Edit: Nvm, I misunderstood this comment.

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You can count the number of pairs having XOR greater than or equal to K instead. Then subtract it from n*(n-1)/2.

Related problem: "Beautiful subarrays" — 665E in Codeforces. You can use Trie to solve this problem.

→ Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Try to think of a relatively easier problem, "How many integers you can find which are giving an XOR of k or less?". Firstly you need to understand that in order to do this in time of O(n) you need to have some algorithm through which you can find this our in O(1) or O(log(n)). In order to find all such integers which are associated with the given list and that would give the resulting XOR of k or less we need to save all the numbers in such a form that we can get the things done in constant time.

Tree-based data structures find their way out from here, so here we need to have some tree-like structures to solve this out and a pretty basic one and fastest one in case of binary representation is TRIE.

Now in order to find the number of elements in the trie which are less than or equal to k we need to have something in our binary representation. So consider the following points:

  1. XOR can be found by altering bits (differing bits) in the binary representation of the numbers.

  2. In order to have a lesser number from a given number (consider x) then you need to reduce the higher-order bits rather than lower-order bits. E.g, if you want to lower value of 111001011 then the most optimal thing to do is to start off by reducing the first bit (higher value causes higher reductions).

  3. A number can be represented in form of a binary string, and a trie is capable of storing any string.

So in order to get the things done and find the number of elements that can give an XOR value less than that of k, we need to think of a situation like how to reduce or increase XOR value by altering the bits.

So your constraint here is k, that is in any condition you do not want to surpass the value of k. Consider the binary representation of k and X and A[i] (0 <= i < A.size()) (the element we are taking XOR with of the elements of the array).

Once we have the representation now insert firstly the elements of the array their binary representation would be 32 bits (integer). Now think about X and k.

We would be traversing a tree and in order to maximise or minimize XOR what can we do?

So when bits of X and A[i] (in trie) becomes same your bit becomes 0 and when they differ it would be 1, so while traversing the tree your utmost importance is that you cannot surpass k,

In order to avoid surpassing K, we would try to reach and prune the possibilities which are not of our interest. Consider this,

If currently you are processing a node and your bit is 1 and your bit of k is 1 then you can "DIFFER YOUR BITS AND KEEP IT SAME AS WELL.". You can take any path 0 or 1 (left or right in trie representation) for your answers, while if a bit of k is 0 then you can only keep the bits the same because you cannot surpass the value of XOR by making the alteration.

if you get bit 1 in X's binary representation and k's bit is also 1 then include the left subtree whole (by adding the count of numbers in it — by augmenting tries)

vbit: the value of a bit of number (X) kbit: the value of bit of k

if (vbit == 1) {
	if (kbit == 1) {
		if (curr -> right != nullptr)
			ans += curr -> right -> counts;
		if (curr -> left != nullptr)
			curr = curr -> left;	
			}		
	else if (curr -> right != nullptr)
				curr = curr -> right;
	}

Similarily vice versa for the bit is 0. The problem can then be simply extended to your problem by iterating over array A.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone give question link

→ Reply