Sumanto's blog

By Sumanto, 2 years 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

| Write comment?
 » 2 years ago, # |   0 Maybe we should use something like sum over subsets dp. Not sure though.
 » 2 years 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)$
•  » » 2 years 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<
•  » » » 2 years ago, # ^ |   +1 I think your code is doing wrong calculations.If i==j, ans should increment by mp[i]*(mp[i]-1)/2 which is the number of combinations when picking 2 out of mp[i] objects.Take example of {1,1,1,1}. The answer should be 6(=4*3/2) and not 4.If i!=j, ans should increment by mp[i]*mp[j].Here's my code, which passed all test cases. long countPairs(const vector& arr) { long ans=0; int mx=0; map mp; for(int ai : arr){ mp[ai]++; mx = max(mx,ai); } for(int i=0; i<=mx; ++i){ if(!mp.count(i)) continue; for(int j=i; j<=mx; ++j){ if(!mp.count(j)) continue; // cout<
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 ...
•  » » » » 2 months ago, # ^ |   0 see carefully he is looping until max(array) correct me if i am wrong