Count All Pairs With Given Xor

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. Input : list = [3, 6, 8, 10, 15, 50], x = 5 Output : 2 Explanatio

Solution 1:

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

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 somej. 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.

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

defget_count(lst, x):
    count_map = create_count_map(lst)
    total_pairs = 0for 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 // 2print(get_count([3, 6, 8, 10, 15, 50], 5))
print(get_count([1, 3, 1, 3, 1], 2))

outputs

2
6

as desired.

Why is this 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.

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) reduces to O(n) time.

Edited to handle duplicates correctly.

Solution 2:

The accepted answer is not giving the correct result for X=0. This code handles that minute error. You can modify it to get answers for other values as well.

defcalculate(a) :

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

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

# Traversing through the array for i in a :

    # Counting frequency
    frequency[i] += 1

answer = 0# Traversing through the frequency arrayfor i in frequency :

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