What would be the most efficient approach to to determine if there exist two integers X and Y in a s-CodePudding

The problem is as below:

Given a sequence of positive integers, SEQ, sorted in ascending order, design and
implement an algorithm with Python to determine if there exist two integers X and Y in
the sorted sequence such that X XNOR Y = -1.

For example, if SEQ is provided to your program as follows:
SEQ:
1 2 3 3 4 4 4 10 10 10

The sample output is given below:
X=3, Y=3
X=4, Y=4
X=4, Y=4
X=4, Y=4
X=10, Y=10
X=10, Y=10
X=10, Y=10
Total match is 7.

I had tried 2 for loops but I would like to find more efficient methods. Any help is much appreciated.

CodePudding user response：

Using itertools and a bit of combinatorics, you can easily do it in O(n):

import math, itertools
data = [1, 2, 3, 3, 4, 4, 4, 10, 10, 10]
total = 0
for k, g in itertools.groupby(data):
    combinations = math.comb(len(list(g)), 2)
    total  = combinations
    print(f"X={k}, Y={k}\n"*combinations, end="")

print("Total =", total)

For int XNOR int = -1, the integers have to be the same (int^int=0 only when both integers are the same, and ~0 == -1).

I therefore group all of the same integers in one pass, and for each group calculate nCr using "(group_length)C2".

Output:

X=3, Y=3
X=4, Y=4
X=4, Y=4
X=4, Y=4
X=10, Y=10
X=10, Y=10
X=10, Y=10
Total = 7