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

Question

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.

Answer 1

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)

Answer 2

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.

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

Answer 3

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)