Sumanto's blog

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

| Write comment?
»
2 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.

»
2 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)$$$

  • »
    »
    2 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;
    
    • »
      »
      »
      2 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;
      }
      
    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      ...

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        see carefully he is looping until max(array) correct me if i am wrong