Lakh's blog

By Lakh, history, 5 months 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  

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can do it with Walsh-Hadamard transform.

»
5 months 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.

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

    ahcl123123123 Can you explain further about the querying part in trie as how to navigate in trie to count the numbers??

»
5 months 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

»
5 months 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.

»
5 months 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one give the implemented code, I am not able to do it.