Подсчитать все пары с данным XOR - PullRequest
Новая
       9

Подсчитать все пары с данным XOR

0 голосов
/ 09 сентября 2018

Дан список размера N. Найдите количество пар (i, j), для которых A [i] XOR A [j] = x и 1 <= i <j <= N. </p>

Ввод: список = [3, 6, 8, 10, 15, 50], х = 5

Выход: 2

Объяснение: (3 ^ 6) = 5 и (10 ^ 15) = 5

Это мой код (перебор): 

import itertools
n=int(input())
pairs=0
l=list(map(int,raw_input().split()))
q=[x for x in l if x%2==0]
p=[y for y in l if y%2!=0]
for a, b in itertools.combinations(q, 2):
    if (a^b!=2) and ((a^b)%2==0) and (a!=b):
        pairs+=1
for a, b in itertools.combinations(p, 2):
    if (a^b!=2) and ((a^b)%2==0) and (a!=b):
        pairs+=1
print pairs

как сделать это более эффективно при сложности O (n) в python?

Ответы [ 2 ]

0 голосов
/ 12 сентября 2018

Принятый ответ не дает правильного результата для X = 0. Этот код обрабатывает эту мелкую ошибку. Вы можете изменить его, чтобы получить ответы и для других значений. 

def calculate(a) :

# Finding the maximum of the array
maximum = max(a)

# Creating frequency array
# With initial value 0
frequency = [0 for x in range(maximum + 1)]

# Traversing through the array 
for i in a :

    # Counting frequency
    frequency[i] += 1

answer = 0

# Traversing through the frequency array
for i in frequency :

    # Calculating answer
    answer = answer + i * (i - 1) // 2

return answer
0 голосов
/ 09 сентября 2018

Заметьте, что если A[i]^A[j] == x, это означает, что A[i]^x == A[j] и A[j]^x == A[i].

Таким образом, решение O (n) состоит в том, чтобы перебрать ассоциированную карту (dict), где каждый ключ - это элемент из A, а каждое значение - это соответствующий счетчик элемента. Затем для каждого элемента рассчитайте A[i]^x и посмотрите, есть ли A[i]^x на карте. Если на карте равно , это означает, что A[i]^A[j] == x для некоторых j. Поскольку у нас есть карта с количеством элементов, равным A[j], общее количество пар будет num_Ai * num_Aj. Обратите внимание, что каждый элемент будет учитываться дважды, так как XOR является коммутативным (т.е. A[i]^A[j] == A[j]^A[i]), поэтому мы должны разделить окончательный счет на 2, так как мы дважды посчитали каждую пару. 

def create_count_map(lst):
    result = {}
    for item in lst:
        if item in result:
            result[item] += 1
        else:
            result[item] = 1
    return result

def get_count(lst, x):
    count_map = create_count_map(lst)
    total_pairs = 0
    for item in count_map:
        xor_res = item ^ x
        if xor_res in count_map:
            total_pairs += count_map[xor_res] * count_map[item]
    return total_pairs // 2

print(get_count([3, 6, 8, 10, 15, 50], 5))
print(get_count([1, 3, 1, 3, 1], 2))

выходы 

2
6

по желанию.

Почему это O (n)?

Преобразование list в dict s.t. дикт содержит количество каждого элемента в списке O (n) раз.

Вычисление item ^ x - это время O (1), а вычисление того, находится ли этот результат за dict, - также время O (1). dict ключ доступа также O (1), как и умножение двух элементов. Мы делаем все это n раз, следовательно, O (n) время для цикла.

O (n) + O (n) сокращается до времени O (n).

Отредактировано для правильной обработки дубликатов.

...