In this HackerEarth The maximum number problem solution You are given an array A of n elements A1, A2, A3, ...,An. Let us define a function F(x) = Sigma(i = 1, n) Ai&x.

Note: Here, & represents bitwise AND operator.

You are required to find the number of different values of x for which F(x) is maximized. There exists a condition for x that it must have exactly l bits sets in its binary representation.

Your task is to find a number of such values for which this function is maximized. Print the required number.

If there are infinite such numbers, then print -1.

It can be proved that under the given constraints the value to be printed is either infinite or not greater than 1e18.


HackerEarth The maximum number problem solution


HackerEarth The maximum number problem solution.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll power(ll x, ll y, ll p)
{
ll res = 1;
x = x % p;
while (y > 0)
{
if (y & 1)
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res;
}
ll modInverse(ll n, ll p)
{
return power(n, p-2, p);
}

ll nCrModPFermat(ll n, ll r, ll p)
{
if (r==0)
return 1;
ll fac[n+1];
fac[0] = 1;
for (int i=1 ; i<=n; i++)
fac[i] = fac[i-1]*i%p;
return (fac[n]* modInverse(fac[r], p) % p *
modInverse(fac[n-r], p) % p) % p;
}
int main() {
ll t;
cin>>t;
while(t--){
ll n,k,i,x,y,z;
ll val=1000000007;
cin>>n>>k;
ll a[n];
for(i=0;i<n;i++){
cin>>a[i];
}
// since k can be atmost 30
ll bits[31];
memset(bits,0,sizeof(bits));
for(i=0;i<n;i++){
z=0;
y=a[i];
while(y!=0){
if(y%2==1){
bits[z]++;
}
z++;
y/=2;
}
}
x=1;
for(i=0;i<=30;i++){
bits[i]*=x;
x*=2;
}
sort(bits,bits+31,greater<int>());
if(bits[k-1]==0){
cout<<-1<<endl;
}
else{
x=bits[k-1];
y=0;
z=0;
for(i=0;i<31;i++){
if(bits[i]==x){
y++;
if(i<k){
z++;
}
}
}
cout<<nCrModPFermat(y, z, val)<<endl;
}

}
return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 hi;

const int maxn = 1e5 + 14, lg = 30;
hi fac(int n){
// cerr << n << '\n';
hi ans = 1;
while(n)
ans *= n--;
return ans;
}
ll c(int n, int r){
return fac(n) / fac(n - r) / fac(r);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while(t--){
int n, l;
assert(cin >> n >> l);
map<int, ll> inc; // bug ll
while(n--){
int x;
assert(cin >> x);
for(int i = 0; i < lg; i++)
inc[i] += x & 1 << i;
}
map<ll, int, greater<ll> > have;
for(int i = 0; i < lg; i++)
have[inc[i]]++;
have.erase(0);
ll ans = 1;
for(auto [v, n] : have){
// cerr << v << ' ' << n << '\n';
int x = min<ll>(l, n);
ans *= c(n, x);
l -= x;
}
cout << (l ? -1 : ans) << '\n';
}
}