### sumantopal07's blog

By sumantopal07, 3 months ago,
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.


• +8

 » 3 months ago, # |   0 Maybe we should use something like sum over subsets dp. Not sure though.
•  » » 3 months ago, # ^ |   0 how to code it?
 » 3 months ago, # |   +5 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)$
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 During the contest i did'nt observed that constraint carefully, that's the mistake i made. Well thanks for Helping BTW. Solution int n; cin >> n; vector ar(n); unordered_map mp; int N = 0; for (auto &i : ar) { cin >> i; mp[i]++; N = max(N, i); } int ans=0; for (int i = 0; i <= N; i++) { for (int j = i; j <= N; j++) { if (i == j && __builtin_popcountll(i & j) == 1 && mp.count(i) && mp.count(j)) { ans += mp[i] ; } else if (__builtin_popcountll(i & j) == 1 && mp.count(i) && mp.count(j)) { ans+=min(mp[i],mp[j]); } } } cout<
•  » » » 7 weeks ago, # ^ | ← Rev. 4 →   0 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.
•  » » » » 7 weeks ago, # ^ |   0 the equality case and the case of i==j is handled using the if condition
•  » » » » » 7 weeks ago, # ^ |   0 I was mentioning that inside the if condition it must be ans+=mp[i]-1 and not ans+=mp[i].
•  » » 3 months ago, # ^ |   0 I was thinking the same way as you were. But i was not able to figure it out. Thanks man yours was nice approach.