Блог пользователя n0h0mo

Автор n0h0mo, история, 14 месяцев назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится