Как быстро подсчитать количество пар в списке, где XOR b больше, чем AND b? ⇐ Python

[Anonymous]

У меня есть массив чисел, я хочу посчитать все возможные комбинации пар, для которых операция xor для этой пары больше, чем операция и.
Пример:< /strong>

Код: Выделить всё

4,3,5,2

возможные пары:[/b]

Код: Выделить всё

(4,3) -> xor=7, and = 0
(4,5) -> xor=1, and = 4
(4,2) -> xor=6, and = 0
(3,5) -> xor=6, and = 1
(3,2) -> xor=1, and = 2
(5,2) -> xor=7, and = 0

Valid pairs for which xor > and are (4,3), (4,2), (3,5), (5,2) so result is 4.

Это моя программа:

Код: Выделить всё

def solve(array):
n = len(array)
ans = 0
for i in range(0, n):
p1 = array[i]
for j in range(i, n):
p2 = array[j]
if p1 ^ p2 > p1 & p2:
ans +=1
return ans

Временная сложность равна O(n^2), но размер моего массива составляет от 1 до 10^5, а каждый элемент в массиве — от 1 до 2^30. Итак, как я могу уменьшить временную сложность этой программы?

Подробнее здесь: https://stackoverflow.com/questions/757 ... -b-is-grea