Solution-

analysis-

          The question asks to find number of pairs for which 
                              [a|b] + [a&b] >=k -(1)
          where [a] = number of set bits in a
          Now we that [a|b]= [a]+[b]-[a&b]

So (1) gets reduced to

[a]+[b] >=k

this can be easily found by keeping a map

`

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
using pi = pair<int, int>;
#define srt(temp) sort(temp.begin(),temp.end())
#define srt1(temp,comp) sort(temp.begin(),temp.end(),comp)
#define f first
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b,c) for(int i=a;i<b;i+=c)
#define rev(i,a,b) for(int i=a;i>b;i--)
#define s second
int log(int x) {
      return 32 - __builtin_clz(x) - 1;
      //return 64 - __builtin_clzll(x) - 1;
 }
const ll mod=(1e9+7);
template<class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vv = vector<vector<T>>;
template<class T> using v = vector<T>;
template<class T> using us = unordered_set<T>;
#define input int t;cin>>t;while(t--)
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//less-ascending
//greater -descending
//less_equal-multiset
#define ordered_set tree<ll,null_type,greater_equal<ll>,rb_tree_tag, tree_order_statistics_node_update> 
//nesx:no of elements smaller than x
//eax:element at x postion
#define nesx order_of_key
#define eax find_by_order
#define sp cout << setprecision(9)
void yes(){cout<<"YES"<<endl;}
void no(){cout<<"NO"<<endl;}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    sp;
    int n;
    cin>>n;
    v<int> hash(32,0),suff(32,0);
    int c;
    rep(i,0,n){
        cin>>c;
        int cnt=0;
        rep(j,0,31){
            cnt+=((c>>j)&1);
        }
        hash[cnt]++;
    }
    // rep(i,0,32)cout<<hash[i]<<" ";
    // cout<<endl;
    int k;
    cin>>k;
    rev(i,31,-1){
        if(i==31)suff[i]=hash[i];
        else suff[i]=suff[i+1]+hash[i];
    }
    // rep(i,0,32)cout<<suff[i]<<" ";
    // cout<<endl;
    ll ans=0;
    rep(i,0,32){
        // cout<<i<<" ";
        if(hash[i]){
            if(i<k){ 
                // cout<<suff[k-i]<<" 1 ";
                if((k-i)>i){
                    ans+=(suff[k-i]*hash[i]);
                }else{
                    ans+=(suff[k-i]-1)*hash[i];
                }
            }else{
                // cout<<(n-1)<<" 2 ";
                ans+=((n-1)*hash[i]);
            }
        }
        // cout<<ans<<endl;
    }
    cout<<(ans/2)<<endl;
}

Hope it will help you

ADD COMMENT • link 6 months ago Abhishek Gupta • 30

Login before adding your answer.