Maximal AND Subsequences

• 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 maximum AND value found so far.
• We also maintain a counter to store the number of times the maximum value has been encountered.
• Whenever the same maximum value is encountered, we increment the counter by one.
• Otherwise, if a greater AND value is found, we update the maximum value and reset the counter to 1.
• In this way, we can find the maximal AND value and also the number of subsequences having this maximal AND value.

Algorithm:

• Let’s assume our recursive function is maximalANDSubsequencesHelper(array, k, index, currentAndVal, maxAndVal, counter) which takes the array, K, current index of the array, AND value generated so far, maximum AND value found so far and the counter to store the number of times the maximum value has been encountered, as arguments respectively.
• Initially, we take the maximum AND value i.e. maxAndVal as -1 and counter as 0.
• Base Condition 1: If k = 0: We have generated a k-element subsequence.
  • If currentAndVal > maxAndVal: Set the maxAndVal to currentAndVal and reset the counter to 1.
  • Otherwise, if currentAndVal = maxAndVal: Increment the counter by 1.
  • Return.
• Base Condition 2: If index = Array.length: We do not have any more elements in the array, so return.
• Now to generate the remaining subsequence, we can either include the Array[index] element in the subsequence or ignore it:
  • Ignore the current element: recursively call  maximalANDSubsequencesHelper(array, k, index + 1, currentAndVal, maxAndVal, counter).
  • Include the current element in the subsequence: recursively call  maximalANDSubsequencesHelper(array, k - 1, index + 1, currentAndVal & Array[index], maxAndVal, counter).
• The above recursive function is called for every index in the array, taking currentAndVal as the corresponding element at the index and index as the current index + 1.
• In the end maxAndVal stores the maximal AND value and counter stores the number of sequences with the maximum value.

• 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.