The task is to find the maximal AND value and the number of subsequences having this maximal AND value.

• Iterate through all possible k-element subsequences of the given array

• Calculate the bitwise AND o...read more

Step 1 : I first applied bubble sort. It was not good enough.
Step 2 : Interviewer asked me to optimise the solution.
Step 3 : Then i gave solution with merge sort and interviewer was happy.

• A brute force approach could be to generate all the possible k-element subsequences using recursion.
• While generating the subsequences we keep track of the current AND value and the maxi...read more

• We do not need to generate all the possible subsequences if we look closely at how the bitwise AND operation works on numbers.
• The AND operation on the ith bit of a sequence gives one for the ith bit, only when all of the numbers in the sequence have their ith bit set.
• The magnitude of a number depends on its most significant bits (MSB).
• So, in order to get the maximum AND value of a subsequence, we want to keep those numbers in the subsequence, for which we can get more number of ones in the most significant bits (MSB) of the result.
• The idea is to iterate over all the bits of the array elements, starting from MSB(most significant bit) to LSB(least significant bit).
• In each iteration, we keep track of the elements for which the current bit is set.
• If the number of such elements is greater than ‘K’, we replace our array elements with these elements and move on to the next iteration.
• In this way, we ensure that we consider only those elements which will make the end result maximum (by making more number of its MSB as one).
• Now, we have the list of elements, for which any k-element subsequence will give the maximum AND value.
• In order to find the number of such subsequences, we calculate the number of ways we can select ‘K’ elements from the list of selected numbers.

Algorithm:

• Create a temporary array, say temp and initialize it with the given array.
• We iterate from the MSF to the LSB:
  • Find all the integers in the temporary array with the current bit set and store them in another array, say setTemp.
  • If setTemp.length >= K, Set temp = setTemp.
• To get the maximum AND value, calculate the bitwise AND of the first ‘K’ elements of temp array.
• To find the number of subsequences with the maximum AND value, we calculate mCk % MOD, where ‘m’ is the number of elements in setTemp, ‘C’ stands for combination and ‘k’ is the length of subsequences. This can be done as follows:
  • mCk % MOD = m! / ((m-k)! * k!) % MOD
  • i.e. mCk % MOD = m! * Inverse((m-k)!) % MOD * Inverse(k!) % MOD
  • For any positive integer P, if MOD is a prime number. Then, Inverse(P) %MOD = P ^ (MOD-2), using Fermat’s Little Theorem.
  • Since MOD is very large, we use binary exponentiation to calculate P ^ (MOD-2).
  • Therefore, mCk % MOD = (m! * ((m-k)!) ^ (MOD - 2) * (k!) ^ (MOD - 2)) % MOD

Note:

• You can refer here for better understanding on how to calculate binomial coefficients modulo large prime.

O(N), where N is the number of elements in the array.

O(N) extra space is required for the temporary array. Hence, the overall space complexity is O(N).

O(N*log(max(Arr[i])), where N is the number of elements in the array and 30 is the maximum number of bits in an integer.

We are iterating over the complete array for every bit. Also, for every bit, we copy the temporary array to another array. So it will take O(N * log(max(Arr[i])) time.
Calculating mCk requires O(M + K + (M-K) + log(10^9 + 7)) i.e. O(M) time i.e. approximately O(N) time. Hence, the overall time complexity is O(N + (N + N)*log(max(Arr[i])) = O(N*log(max(Arr[i])).

/*
	Time complexity: O(N * log(max(Arr[i])))
	Space Complexity: O(N)
	
	Where N is the number of elements in the array.
*/

import java.util.ArrayList;

public class Solution {
	private static long MOD = (long) 1e9 + 7;

	private static long binaryExp(long a, long b) {
		a = a % MOD;

		// Calculate a^b using binary exponentiation.
		long res = 1;

		while (b > 0) {
			if ((b & 1) != 0) {
				res = (res * a) % MOD;
			}
			a = (a * a) % MOD;
			b = b >> 1;
		}

		return (int) res;
	}

	private static long factorial(long n) {
		// Calculate factorial of 'n'.
		long ans = 1;
		for (int i = 1; i <= n; i++) {
			ans = (ans * i) % MOD;
		}
		return (int) ans;
	}

	public static ArrayList maximalANDSubsequences(ArrayList arr, long k) {

		ArrayList temp = new ArrayList(arr);

		// Iterate over all the bits of the array elements, starting from MSB to LSB.
		for (int i = 30; i >= 0; --i) {
			ArrayList setTemp = new ArrayList();

			long n = temp.size();
			for (int j = 0; j < n; j++) {
				// Keep track of the elements in "temp" for which the current bit is set.
				if ((temp.get(j) & ((int) 1 << i)) != 0) {
					setTemp.add(temp.get(j));
				}
			}

			if (setTemp.size() >= k) {
				// Replace the old array elements with the new ones.
				temp = setTemp;
			}
		}

		// Calculating max AND value.
		long maxVal = temp.get(0);

		for (int i = 1; i < k; i++) {
			maxVal = (maxVal & temp.get(i));
		}

		// Find number of possible subsequences by calculating mCk % MOD.
		// mCk % MOD = (m! * ((m-k)!) ^ (MOD - 2) * (k!) ^ (MOD - 2)) % MOD

		long m = temp.size();

		long mFact = factorial(m);
		long mMinusKFact = factorial((m - k));
		long kFact = factorial(k);

		long inverseOfmMinusKFact = binaryExp(mMinusKFact, MOD - 2);
		long inverseOfkFact = binaryExp(kFact, MOD - 2);

		long count = (mFact * inverseOfmMinusKFact) % MOD;

		count = (count * inverseOfkFact) % MOD;

		ArrayList ans = new ArrayList();
		ans.add((int) maxVal);
		ans.add((int) count);

		return ans;
	}
}

/*

	Time complexity: O(N * log(max(Arr[i])))

	Space Complexity: O(N)

	

	Where N is the number of elements in the array.

*/



const int MOD = 1000000007;



int binaryExp(long long a, long long b)

{

    a = a % MOD;



    // Calculate a^b using binary exponentiation.

    long long res = 1;



    while (b > 0)

    {

        if (b & 1)

        {

            res = (res * a) % MOD;

        }

        a = (a * a) % MOD;

        b = b >> 1;

    }



    return res;

}



int factorial(int n)

{

    // Calculate factorial of 'n'.

    long long ans = 1;

    for (int i = 1; i <= n; i++)

    {

        ans = (ans * i) % MOD;

    }

    return ans;

}



vector maximalANDSubsequences(vector &arr, int k)

{



    vector temp = arr;



    // Iterate over all the bits of the array elements, starting from MSB to LSB.

    for (int i = 30; i >= 0; --i)

    {

        vector setTemp;



        int n = temp.size();

        for (int j = 0; j < n; j++)

        {

            // Keep track of the elements in "temp" for which the current bit is set.

            if (temp[j] & (1LL << i))

            {

                setTemp.push_back(temp[j]);

            }

        }



        if (setTemp.size() >= k)

        {

            // Replace the old array elements with the new ones.

            temp = setTemp;

        }

    }



    // Calculating max AND value.

    int maxVal = temp[0];



    for (int i = 1; i < k; i++)

    {

        maxVal = maxVal & temp[i];

    }



    // Find number of possible subsequences by calculating mCk % MOD.

    // mCk % MOD = (m! * ((m-k)!) ^ (MOD - 2) * (k!) ^ (MOD - 2)) % MOD



    int m = temp.size();



    int mFact = factorial(m);

    int mMinusKFact = factorial(m - k);

    int kFact = factorial(k);



    int inverseOfmMinusKFact = binaryExp(mMinusKFact, MOD - 2);

    int inverseOfkFact = binaryExp(kFact, MOD - 2);



    int count = ((long long)mFact * inverseOfmMinusKFact) % MOD;



    count = ((long long)count * inverseOfkFact) % MOD;



    vector ans = {maxVal, count};



    return ans;

}

'''
    Time complexity: O(N * log(max(Arr[i])))
	Space Complexity: O(N)
	
	Where N is the number of elements in the array.
'''

MOD = 1000000007


def binaryExp(a, b):
    a = a % MOD
    # Calculate a^b using binary exponentiation.
    res = 1

    while (b > 0):
        if(b & 1):
            res = (res*a) % MOD
        a = (a*a) % MOD
        b = b >> 1

    return res


def factorial(n):
    # Calculate factorial of 'n'.
    ans = 1
    for i in range(1, n+1):
        ans = (ans*i) % MOD

    return ans


def maximalANDSubsequences(arr, k):
    temp = arr

    # Iterate over all the bits of the array elements, starting from MSB to LSB.
    for i in range(30, -1, -1):
        setTemp = []
        n = len(temp)
        for j in range(n):
            # Keep track of the elements in "temp" for which the current bit is set.
            if (temp[j] & (1 << i)):
                setTemp.append(temp[j])

        if (len(setTemp) >= k):
            # Replace the old array elements with the new ones.
            temp = setTemp

    # Calculating max AND value.
    maxVal = temp[0]

    for i in range(1, k):
        maxVal = maxVal & temp[i]

    # Find number of possible subsequences by calculating mCk % MOD.
    # mCk % MOD = (m! * ((m-k)!) ^ (MOD - 2) * (k!) ^ (MOD - 2)) % MOD

    m = len(temp)

    mFact = factorial(m)

    mMinusKFact = factorial(m - k)
    kFact = factorial(k)

    inverseOfmMinusKFact = binaryExp(mMinusKFact, MOD - 2)
    inverseOfkFact = binaryExp(kFact, MOD - 2)

    count = (mFact * inverseOfmMinusKFact) % MOD

    count = (count * inverseOfkFact) % MOD

    ans = [maxVal, count]

    return ans