n0h0mo's blog

By n0h0mo, history, 6 months ago, In English

Hi, I spent one day for this problem but I haven't come up with solution for this problem. Can you take a look at this problem? Thanks.


Given an array which have $$$n \leq 10^5$$$ elements which values are $$$\leq 2^{16}$$$, count all pairs in array which differ in exactly $$$K \leq 16$$$ bits of binary representation of both the numbers.

Sample Input:

5 2
2 4 1 3 1

Sample Output:


Explanation: $$$(a_1, a_3); (a_1, a_2); (a_1, a_5); (a_2, a_3); (a_2, a_5)$$$

Link: https://www.spoj.com/PTIT/problems/P186PROF/ (in Vietnamese since I can't find any other links). Test case for this problem in SPOJ is weak, since I got accepted with time complexity $$$O(n \times \binom{16}{k})$$$. But this is not the intended soluton, maybe.

Full text and comments »

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