HackerEarth The maximum number problem solution

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.

#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';
    }
}