Optimizing Python Code for Finding Index Pairs Meeting Specific Inequality

Question

I have a Python code that efficiently solves my task, but I'm concerned about its time complexity. The task is to find the number of index pairs (i, j) where the inequality aᵢ ⊕ aʲ ≥ bᵢ ⊕ bʲ holds true, given two arrays of integers "a" and "b," each of length "n." Here, ⊕ denotes the XOR operation.

Here's my current implementation:

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

count = 0

for i in range(n):
    for j in range(n):
        if a[i] ^ a[j] >= b[i] ^ b[j]:
            count += 1

print(count)

While this code works well for small inputs, I'm concerned about its performance for larger arrays due to its nested loop structure, resulting in a time complexity of O(n²). I'm seeking suggestions on how to optimize this code to improve its runtime efficiency, particularly for larger input sizes.

Any insights or alternative approaches that could achieve better time complexity would be greatly appreciated.

Answer 1

Improved the efficiency of code using Numpy.
Comparison :

• Your code for 10K entries on a and b, run time: 0:00:46.925000
• Code based on NumPy for 10K entries on a and b, run time: 0:00:00.453003 i.e., almost 100 times faster

import datetime
import numpy as np

n = 10000
a = [1,2,3,4,5,16,17,18,19,20] * int(n/10)  # List with 10 K items created for testing
b = [10,9,8,7,6,11,12,13,14,15] * int(n/10)  # List with 10 K items created for testing

print("Len a : ", len(a))
print("Len b : ", len(b))

######### Your Code Test ######################
count = 0
print("Starting your code test")
start = datetime.datetime.now() # Start time
for i in range(n):
    for j in range(n):        
        if a[i] ^ a[j] >= b[i] ^ b[j]:
            count += 1

end = datetime.datetime.now() # end time
delta = end-start 
     
print("Your code time delta : ", delta)
print("Result : ", count)


############## New Code test #######################

count = 0
print("Starting new code test")
start = datetime.datetime.now() # Start time

a_arr = np.array(a).reshape(-1,1)
a_arr_biwise = np.bitwise_xor(a_arr, a_arr.transpose())  #bitwise XOR of array on itself

b_arr = np.array(b).reshape(-1,1)
b_arr_biwise = np.bitwise_xor(b_arr, b_arr.transpose())  #bitwise XOR of array on itself

comparison_matrix = np.greater_equal(a_arr_biwise,b_arr_biwise) # axor >= bxor comparison on each position.
count = comparison_matrix.sum() # find True count , i.e. where >= is True

end = datetime.datetime.now() # end time
delta = end-start      

print("New code time delta : ", delta)
print("Result : ", count)

output

Len a :  10000
Len b :  10000
Starting your code test
Your code time delta :  0:00:46.925000
Result :  80000000
Starting new code test
New code time delta :  0:00:00.453003
Result :  80000000

Can see that the result is the same for both codes.