1

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.

aloy
  • 13
  • 1
  • 3
  • Why is `X=3;Y=3` exists only once and the `X=4;Y=4` exists 3 times? – Bharel Mar 19 '22 at 14:04
  • X=4;Y=4 exists 3 times, as there is 3 instances of 4; 4(1), 4(2), 4(3), such that 4(1) = 4(2), 4(1) = 4(3), and 4(2) = 4(3). – aloy Mar 19 '22 at 14:22

1 Answers1

-1

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
Bharel
  • 23,672
  • 5
  • 40
  • 80