Count pairs which differ in K bits

Revision en1, by n0h0mo, 2023-03-27 14:26:16

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.

Statements:

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:

5

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.

Tags bitwise

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English n0h0mo 2023-03-27 14:26:16 858 Initial revision (published)