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

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | OO0OOO00O0OOO0O0…O | 3280 |

3 | Syloviaely | 3274 |

4 | Petr | 3233 |

5 | Um_nik | 3213 |

6 | ko_osaga | 3124 |

7 | Benq | 3105 |

8 | Swistakk | 3092 |

9 | fjzzq2002 | 3055 |

10 | anta | 3053 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 170 |

2 | rng_58 | 162 |

3 | tourist | 159 |

4 | Petr | 153 |

5 | Swistakk | 152 |

6 | csacademy | 151 |

7 | Vovuh | 145 |

7 | Um_nik | 145 |

9 | Errichto | 144 |

10 | PikMike | 143 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/20/2018 10:44:10 (f2).

Desktop version, switch to mobile version.

User lists

Name |
---|

You can do it with Walsh-Hadamard transform.

hellman_ I don't know about this transform. Please suggest some link or pre-requisites to understand the Walsh-Hadamard transform.

https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it

What are the constraints? FWHT would work in

n2^{n}wherenis the number of bits in the maximum value in the array.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.

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

It can be solved using trie see the link for details

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.

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.