```
given an array of non-negative integers, count the number of unordered pairs of array elements such that their bitwise AND(&) is a power of 2.
```

```
for ex: for array [10,7,2,8,3]; there are 6 unordered pairs;
explaination:
10&7=2
10&2=2;
10&8=2;
10&3=2;
7&2=2;
2&3=2;
```

Constraints:
1<=n<=2*10^5
0<=ar[i]<=2^12

```
This was asked in Hackerank intermediate certification Test.I failed to come up with linear time solution.
```

Maybe we should use something like sum over subsets dp. Not sure though.

how to code it?

Since the numbers are small (<=4096), you can simply try every pair of possible numbers and check if they are a valid pair. If they are just add to the answer how many times you have this pair in your array (if the numbers are $$$A$$$ and $$$B$$$, you need to add count($$$A$$$)*count($$$B$$$),attention if $$$A=B$$$). Complexity $$$O(Amax*Amax)$$$

During the contest i did'nt observed that constraint carefully, that's the mistake i made. Well thanks for Helping BTW. Solution

I guess there are corrections in your code:

1.In the second for loop:j must start from i+1.

2.If both a[i] && a[j] are the same, then ans must be increased by (mp[i]-1).

I too couldn't solve in time but after seeing your approach I got the idea.

the equality case and the case of i==j is handled using the if condition

I was mentioning that inside the if condition it must be ans+=mp[i]-1 and not ans+=mp[i].

I was thinking the same way as you were. But i was not able to figure it out. Thanks man yours was nice approach.