XOR greater than 4 of even-even or odd odd pair

Given an array of even and odd numbers, I want to get the number of (even-even) and (odd-odd) pairs whose XOR is greater than or equal to 4. I tried this with the code below but it runs in O(n^2), (yikes). Please can anyone suggest a means of optimization?

n = int(raw_input()) #array size

ar = map(int, raw_input().split()) #the array

cnt = 0

for i in xrange(len(ar)):

for j in xrange(i+1, len(ar)):

if ar[i] ^ ar[j] >= 4 and (not ar[i] & 1 and not ar[j] & 1):

cnt += 1; #print ar[i],ar[j],ar[i]^ar[j];

elif ar[i] ^ ar[j] >= 4 and (ar[i] & 1 and ar[j] & 1):

cnt += 1
print cnt


EDIT: I discovered something. any number x, which gives a remainder after % 4, i.e x % 4 != 0, will result to 2 when XORed to a number -2 itself. For example, 6. It is not divisible by 4, therefore, 6 XOR 6-2 (4),==> 2. 10 is not divisible by 4, hence, 10 XOR 10-2 (8) ==> 2. Can you please tell me how this could help me optimize my code? I just know now that I will just look for numbers divisible by 4 and find the count of their + 2.

O(nlog(n))

3 Answers
3

For simplicity, let´s assume the array does not have duplicates. For the XOR between 2 numbers to be >= 4, they need to have any different bit (excluding lower 2 bits). Given that we already know they are even-even or odd-odd pairs, their lowest bit is the same.

Note that for any number X, X XOR (X + 4 + k) will always be >= 4. So the problem is considering what happens with X XOR (X + 1), X XOR (X + 2) and X XOR (X + 3).
X XOR (X + 1) will be >= 4 when the third lowest bit has changed by adding only 1. That means, we had X ending in 011 so X + 1 ends in 100 or we had X ending in 111 so X + 1 ends in 000. In both cases, this means X % 4 = 3. In any other case (X % 4 != 3), X XOR (X + 1) will be < 4.

For X XOR (X + 2) to be >= 4, the third lowest bit has changed by adding 2. This means, X ended in 011, 010, 111, or 110. So we now have X % 4 = 3 or X % 4 = 2.

For X Xor (X + 3) to be >= 4, the third lowest bit has changed by adding 3. This means, X ended in 011, 010, 001, 111, 110, 101. So we now have X % 4 = 3, X % 4 = 2 or X % 4 = 1.

Here is pseudocode:

for each element in array:
count[element] += 1
total += 1
for each X in sorted keys of count:
if X % 4 == 3:
answer += count[X + 1] + count[X + 2] + count[X + 3]
if X % 4 == 2:
answer += count[X + 2] + count[X + 3]
if X % 4 == 1:
answer += count[X + 3]
total -= count[X]
answer += total - (count[X + 1] + count[X + 2] + count[X + 3]) # all X + 4 + K work


To account for duplicates, we need to avoid counting a number against itself. You will need to keep the count of each number, and do the same as the above with the modification that the answer will be the count of that number * (all the others - the amount of X + 2 numebers)

You should work on separating your code, one improvement is the use of set to avoid repeating operations, although it may get more memory overhead.

set

import random
from operator import xor
import itertools

random.seed(10)

in_values = [random.randint(0, 10) for _ in range(100)]

def get_pairs_by(condition, values):
odds = set(filter(lambda x: x % 2 == 0, values))
evens = set(filter(lambda x: x % 2 == 1, values))
def filter_pairs_by_condition(values):
return (
(x, y) for x, y in set(
map(lambda x: tuple(sorted(x)),
itertools.product(iter(values), iter(values))))
if condition(xor(x, y))
)
return list(
itertools.chain.from_iterable(
(filter_pairs_by_condition(x) for x in (odds, evens))
)
)


print(get_pairs_by(lambda x: x >= 4, in_values))


The keypoint is:

set(map(lambda x: tuple(sorted(x)),
itertools.product(iter(values), iter(values)))))


What we are doing is that pairs of (5, 7) and (7, 5) should be evaluated as being the same, so we take rid of them there.

Here you have the live example

EDIT:
As a quick update to your code, you can use a dictionary to memoize previously computed pairs, hence:

n = int(raw_input()) #array size

ar = map(int, raw_input().split()) #the array

cnt = 0

prev_computed =

for i in xrange(len(ar)):

for j in xrange(i+1, len(ar)):
if any(x in prev_compued for x in ((ar[i], ar[j]), (ar[j], ar[i]))):
cnt += 1
continue

if ar[i] ^ ar[j] >= 4 and (not ar[i] & 1 and not ar[j] & 1):
cnt += 1; #print ar[i],ar[j],ar[i]^ar[j];
prev_computed[(ar[i], ar[j])] = True
prev_computed[(ar[j], ar[i])] = True
elif ar[i] ^ ar[j] >= 4 and (ar[i] & 1 and ar[j] & 1):
cnt += 1
prev_computed[(ar[i], ar[j])] = True
prev_computed[(ar[j], ar[i])] = True

print cnt


bigO

def xor_sum(lst)
even_dict = a dictionary with keys being all even numbers of lst and values being their frequencies
odd_dict = a dictionary with keys being all odd numbers of lst and values being their frequencies
total_even_freq = sum of all frequencies of even numbers
total_odd_freq = sum of all frequencies of odd numbers
even_res = process(even_dict, total_even_freq)
odd_res = process(odd_dict, total_odd_freq)
return even_res + odd_res

def process(dict, total_freq)
res = 0
for num in dict.keys
# LSB of XOR of 2 even numbers is always 0
# Let p = XOR of 2 even numbers; if p < 4 then p = 00000000 (minus_2) or 00000010 (plus_2)
plus_2 = num+2
minus_2 = num-2
count = 0
if( (plus_2 XOR num) < 4 and (plus_2 is a key of dict) )
count = count + frequency_of_plus_2
if( (minus_2 XOR num) < 4 and (minus_2 is a key of dict) )
count = count + frequency_of_minus_2
count = count + num
res = res + (total_freq+1-count)
return res


Complexity:

Assuming you have a good hash function for your dictionaries (a hashmap), the average time complexity is O(n)

hash function

dictionaries

hashmap

O(n)

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.