arrays sum AND in data stuctures

Question

Antonio got an array A for his christmas present. Array A consists of N positive integers.

He wants to give a pair of integers from this array to his girlfriend Teena.

Teena likes a pair of integers (a,b) if and only if (a+b)/2 equals the bitwise AND of a and b. In other words Teena likes an integer pair (a,b) if and only if (a+b)/2 = Bitwise AND(a,b) holds.

Now Antonio wants to find the number of pairs he can gift to Teena such that she likes it. Note that an element of the array can be a part of atmost one pair.

As Antonio is weak in arrays he asked you for help. Help Him !

Input Format

First line contains a single integer denoting N.

Next line contains N space separated integers denoting the elements of array A.

Output Format

Print the number of pairs Antonio can gift to Teena such that she likes it.

Constraints

1<=N<=105

1<=Ai<=109

Answer 1

There are two ways to answer this question, one which just iterates through the set of numbers and does the comparison above, and one that provides the technically optimal solution by comparing all possible outputs.

Without doing the math, we can visualize the difference mentally, consider this example:

1 2 3 4 5 6 7 8

Let's say we select (1, 2) and (4, 7) from our list, none of the other numbers match the description. We got there by starting at the first number and evaluating everything after it. Again, I'm not actually doing the calculation here, just imagining.

There is also a world where if we instead skipped the first number, we get (2, 3), (4,5), (6,7). That's three pairs - one more than the previous. See the problem? The answer may depend on which numbers you evaluate, in which order. The problem then devolves into a discrete math problem instead of a coding one, where we then go on to evaluate decision trees and other stuff like that.

I'm a computer scientist, not a discrete mathematician, so let's do it the first way and call it a day.

# Creating a list instead of reading it for simplicity

my_list = list(range(1, 110))

# Assume each number only appear once in our list

# [0, 1, 2, 3, 4, 5, 6, 7, 8, ..., 109]

blacklist = []

counter = 0

for a in my_list:

for b in my_list:

if int((a+b)/2) == a & b:

if a in blacklist or b in blacklist:

continue # Skip this pair and move on to the next

else:

print("Found: ", a, b)

blacklist.append(a)

blacklist.append(b)

counter += 1

print(counter)

"""

Sample Output:

Found: 0 0

Found: 1 1

Found: 2 2

Found: 3 3

Found: 4 4

Found: 5 5

Found: 6 6

Found: 7 7

Found: 8 8

Found: 9 9

Found: 10 10

Found: 11 11

...

"""

We basically compare every number in the list to every other number in the list, and if it finds a pair, print that pair and then add those two numbers to the blacklist so they can't be used again the next time around.

Technically this produces a solution that makes every number appear as a pair, such as (0, 0) and (1, 1) etc being valid pairs for Teena, since they meet the condition. The problem also does not say a single number can only appear in the pair once, just that it can only be in one pair, so a number could (and does) appear in a single pair twice.

We can fix this by adding an if statement to check if the two numbers are equal, and continue the calculation:

for a in my_list:

for b in my_list:

if a == b: continue

if int((a+b)/2) == a & b:

...

"""

Found: 0 1

Found: 2 3

Found: 4 5

Found: 6 7

Found: 8 9

Found: 10 11

"""

This does change our answer, and gives us 55 entries instead of 110 from the previous version.