Sumanto's blog

BIT MANIPULATION PROBLEM(HACKERANK INTERMEDIATE TEST PROBLEM)
By Sumanto, 5 years ago, In English 
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.
  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like 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)$$$

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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<int> ar(n);
    unordered_map<int, int> 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<<ans;
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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<int>& arr) {
    long ans=0;
    int mx=0;
    map<int,int> 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<<i<<':'<<mp[i]<<','<<j<<':'<<mp[j]<<'\n';
            if(__builtin_popcountll(i&j)==1){
                if(i==j) ans+=((long(mp[i])*(mp[i]-1))/2);
                else
                ans+= (long(mp[i])*mp[j]);
            }
        }
    }
    return ans;
}
      → Reply