Question: ZSCALER, Online Assessment Questions | BITS Archive | 2023
0
Entering edit mode

Entering edit mode
0

Which college?

ordinary_man
• 0
2
Entering edit mode

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;
}
``````