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