407665: GYM102868 C Dark-Green

Dark-Green is working on the divert power task when he realizes that there are a lot of rooms that currently require power diverted to them. Specifically, there are $$$n$$$ rooms that Dark-Green must divert power to and the $$$i$$$th room has $$$a_{i}$$$ pieces of electronics which require power.

However, due to the strange effects of space travel, he realizes that the amount of power that each room needs is not linear in the number of devices present in the room. He deduces the following recursive function $$$f(x)$$$ defining the amount of power the room needs when there are $$$x$$$ devices in the room:

• $$$f(0) = 0$$$
• $$$f(2 \cdot x) = f(x)$$$
• $$$f(2 \cdot x + 1) = f(x) + 1$$$

Given this, Dark-Green would like to figure out the number of unique pairs of the $$$n$$$ rooms that require the same amount of power.

The first line of input will contain $$$n$$$ which is the number of rooms that require power diverted to them ($$$1 \leq n \leq 10^{4}$$$).

The second line of input will contain $$$n$$$ space-separated integers where the $$$i$$$th integer, $$$a_i$$$, represents the number of devices room $$$i$$$ requires ($$$0 \leq a_i \leq 10^{9}$$$).

A single integer representing the number of unique pairs of rooms that need the same amount of power.

3
1 2 4

3

4
5 0 0 2

1

In the first example, computing $$$f(x)$$$ for all the values in the array yields us the same answer for all of them so any pair works and so there are $$$3$$$ unique pairs.