用给定的 XOR 计算所有对 [英] Count all pairs with given XOR

问题描述

给定一个大小为 N 的列表.找出对 (i, j) 的数量，使得 A[i] XOR A[j] = x，并且 1 <= i <;j <= N.

Given a list of size N. Find the number of pairs (i, j) such that A[i] XOR A[j] = x, and 1 <= i < j <= N.

输入:列表 = [3, 6, 8, 10, 15, 50], x = 5

Input : list = [3, 6, 8, 10, 15, 50], x = 5

输出:2

解释:(3 ^ 6) = 5 和 (10 ^ 15) = 5

Explanation : (3 ^ 6) = 5 and (10 ^ 15) = 5

这是我的代码(蛮力):

This is my code (brute force):

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 中更有效地做到这一点?

how to do this more efficiently in a complexity of O(n) in python?

推荐答案

观察如果 A[i]^A[j] == x，这意味着 A[i]^x == A[j] 和 A[j]^x == A[i].

Observe that if A[i]^A[j] == x, this implies that A[i]^x == A[j] and A[j]^x == A[i].

因此，O(n) 解决方案是遍历关联映射 (dict)，其中每个键是 A 中的一个项目，每个值是各自的项的计数.然后，对于每一项，计算A[i]^x，看看A[i]^x是否在地图中.如果它在地图中是，这意味着 A[i]^A[j] == x 对于 some j.由于我们有一个地图，其中包含等于 A[j] 的所有项目的计数，因此对的总数将为 num_Ai * num_Aj.请注意，每个元素都会被计数两次，因为 XOR 是可交换的(即 A[i]^A[j] == A[j]^A[i])，所以我们必须除以最后的计数 2，因为我们已经重复计算了每一对.

So, an O(n) solution would be to iterate through an associate map (dict) where each key is an item from A and each value is the respective count of the item. Then, for each item, calculate A[i]^x, and see if A[i]^x is in the map. If it is in the map, this implies that A[i]^A[j] == x for some j. Since we have a map with the count of all items that equal A[j], the total number of pairs will be num_Ai * num_Aj. Note that each element will be counted twice since XOR is commutative (i.e. A[i]^A[j] == A[j]^A[i]), so we have to divide the final count by 2 since we've double counted each pair.

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) 时间.

Converting a list to a dict s.t. the dict contains the count of each item in the list is O(n) time.

计算item ^ x是O(1)时间，计算这个结果是否在dict中也是O(1)时间.dict 键访问也是 O(1)，两个元素的乘法也是如此.我们做了 n 次，因此循环的时间为 O(n).

Calculating item ^ x is O(1) time, and calculating whether this result is in a dict is also O(1) time. dict key access is also O(1), and so is multiplication of two elements. We do all this n times, hence O(n) time for the loop.

O(n) + O(n) 减少到 O(n) 时间.

O(n) + O(n) reduces to O(n) time.

已编辑以正确处理重复项.

Edited to handle duplicates correctly.

这篇关于用给定的 XOR 计算所有对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！