0

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

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

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

melpomene
  • 84,125
  • 8
  • 85
  • 148
Max Daen
  • 21
  • 4
  • @MaharshiRoy You don't need a trie to do this, just a set. I'm not sure you understand what a trie is. Please see my answer below – Matt Messersmith Sep 09 '18 at 18:19
  • If you properly follow the [reference](https://en.cppreference.com/w/cpp/container/unordered_set/insert), the complexity section lists O(n) time for insertion. In the worst case, hashing fails to provide O(1) if same bucket gets filled continuously. I competitive programming, I have got TLE several times due to this. Trie guarantees O(bit-depth) ~ O(1) insertion. Thus overall O(n) – Maharshi Roy Sep 09 '18 at 18:32
  • Check this [answer](https://stackoverflow.com/questions/7351459/time-complexity-of-python-set-operations) @Messersmith – Maharshi Roy Sep 09 '18 at 18:34

2 Answers2

0

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 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))

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.

Matt Messersmith
  • 12,939
  • 6
  • 51
  • 52
0

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. 

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
Negativ3
  • 62
  • 8