The maximum number

You are given an array $A$ of $n$ elements $A_1,A_2,A_3,...,A_n$. Let us define a function $F(x)=\sum _{i=1}^n{A}_i\mathrm{\&}x$.

Note: Here, $\mathrm{\&}$ 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. 

Example:

Input:  n=5, l=2, arr = { 3, 5, 7, 1, 4 }
Output: 2

Approach

Java

import java.util.Comparator;
import java.util.TreeMap;

public class TheMaxNum {

    public static void main(String[] args) {

        int n = 5;
        int l = 2;
        long[] arr = { 3, 5, 7, 1, 4 };
        long maxOr = 0, maxBit = 0;
        int[] bits = new int[32];
        for (int i = 0; i < n; i++) {
            maxOr |= arr[i];
            long no = arr[i];
            int pos = 0;
            while (no > 0) {
                bits[pos++] += (no & 1) == 0 ? 0 : 1;
                no >>= 1;
            }
        }
        while (maxOr > 0) {
            if ((maxOr & 1) == 1) {
                maxBit += 1;
            }
            maxOr >>= 1;
        }
        if (maxBit == l)
            System.out.println(1);
        else if (l > maxBit)
            System.out.println(-1);
        else {
            long ans = resolve(bits, l);
            System.out.println(ans);
        }
    }

    static private long resolve(int[] bits, int l) {
        TreeMap<Long, Long> treeMap = new TreeMap<>(Comparator.reverseOrder());
        for (int i = 0; i < 31; i++) {
            long y = (1L << i) * bits[i];
            treeMap.put(y, treeMap.getOrDefault(y, 0L) + 1);
        }
        long result = 0;
        for (Long key : treeMap.keySet()) {
            Long val = treeMap.get(key);
            if (val + result < l)
                result += val;
            else {
                return nCr(val, l - result);
            }
        }
        return -1;
    }

    static private long nCr(long n, long r) {
        long res = n;
        for (long i = 2; i <= r; i++) {
            res = (res * (n - i + 1)) / i;
        }
        return res;
    }

}