# Problem Link:

# Difficulty:

Simple

# Pre-requisites:

Binary Notation, Binary AND operation

# Problem:

You are given a sequence of **N** integer numbers **A**. Calculate the sum of **A[i] AND A[j]** for all the pairs (**i**, **j**) where **i** < **j**.

# Explanation:

## Solution to the sub tasks 1 and 3:

If you take a look at the **AND** function for all possible pairs of numbers in the sequence - 0,0; 0,1; 1,0; 1,1 - you will notice that AND equals to one **only in case both arguments equal to one**, otherwise it equals to zero and will not change the answer in any way. Thus, you just have to calculate the number of pairs (**i**, **j**) where **i** < **j** and both the **i**-th and the **j**-th numbers equal to one. Naturally, the answer equals to **o * (o - 1) / 2**, where **o** is the number of ones in the sequence.

## Solution to the sub task 2:

In this sub task the constraints are designed in such a way that you can just do the brute force among all the pairs (**i**, **j**) where **i** < **j** and add the value of the **i**-th number **AND** the **j**-th number to the answer. That will do.

## Solution to all the sub tasks:

Let’s use the observation that we had in sub task 3, **AND** of two binary values is a natural number only in case both of them are **true**. Another observation is that in some exact bit of the result, **AND** depends **only on this bit in its arguments**. That gives rise to the following solution: let’s solve the problem **bit-by-bit**. At first, let’s count the number of nonzero **0**-th bits - we will call this number **f(0)**. Then, there are **f(0) * (f(0)-1)/2** ways to add **2^0** to the answer. Generally, there will be **f(i)*(f(i)-1)/2** ways to add **2^i** to the answer, where **f(i)** is the number of numbers in the sequence that contain **2^i** in their binary representation. Therefore, the final formula is the sum of **f(i) * f(i-1)/2 * 2^i** over all possible values of **i**. The maximal possible value of **i** equals to **29** here, as it is a binary logarithm of maximal possible value in the sequence.

#### Common bugs

Subtask 3: **cnt * (cnt-1)/2** will overflow for **cnt** = 10^5. “long” datatype is 32 bits in C++

# Setter’s solution:

Solution to sub tasks 1 and 3 can be found here

Solution to sub tasks 1 and 2 can be found here

Solution to all the subtasks can be found here

# Tester’s solution:

Can be found here