确定排序序列中是否存在两个整数X和Y，使得XNOR Y=-1，最有效的方法是什么

Question

问题如下：

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.

我已经尝试了2个for循环，但我想找到更有效的方法。非常感谢您的帮助。

Answer 1

使用itertools和一些组合数学，您可以在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)

对于int XNOR int = -1，整数必须相同(仅当两个整数相同时为int^int=0，并且为~0 == -1(。

因此，我在一次遍历中对所有相同的整数进行分组，并且对于每个组使用"n"来计算nCr；(group_length)C2"；。

输出：

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