sumantopal07's blog

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

»
3 months 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.

»
3 months 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)$$$

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

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