Maximal AND Subsequences

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
42 upvotes
Asked in company
Amazon

Problem statement

You are given an array consisting of N integers. You need to find the number of k-element subsequences of the given array where the bitwise AND of the subsequence's elements is maximal. Also, find the maximal AND value.

Example:

Let the array be [1, 3, 6, 7] and K=3. The possible k-element subsequences of the given array are: {1, 3, 6}, {1, 3, 7}, {1, 6, 7}, {3, 6, 7}. Applying AND operation on all possible subsequences we get values: 0, 1, 0, 2 respectively. The maximal AND value of these subsequences is 2, and only 1 subsequence {3, 6, 7} has this value.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains two space-separated integers ‘N’ and ‘K’ denoting the number of elements present in the array and the length of the subsequences.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.
Output format: 
For each test case, two space-separated integers are printed denoting the maximal AND value and the number of subsequences having maximal AND value, respectively.

Output for each test case is printed on a separate line.
Note: 
The number of possible k-element subsequences having that maximal AND value can be very large. So, print the answer modulo 1000000007.

You do not need to print anything, it has already been taken care of. Just return an array of size two where the 1st element is max AND value and 2nd element is the number of subsequences having this maximal AND value.
Constraints: 
1 <= T <= 10
2 <= N <= 5 * 10^4
2 <= K <= N
0 <= Arr[i] <= 10^8

Where  ‘T’ represents the number of test cases, ‘N’ represents the number of elements present in the array and ‘K’ represents the length of the subsequences.

Time Limit: 1 sec
Sample Input 1:
2
4 3
1 3 6 7
3 2
9 9 9
Sample Output 1:
2 1
9 3
Explanation 1:
For the first test case refer to the example explained above.

For the second test case we have, array: [9, 9, 9], N = 3 and K = 2. The possible k-element subsequences of the given array are: {9, 9}, {9, 9}, {9, 9}. Applying AND operation on all possible subsequences we get values: 9, 9, 9 respectively. The maximal AND value of these subsequences is 9, and all subsequences have this value.
Sample Input 2:
2
5 2
1 2 3 4 5
4 4
6 3 7 0
Sample Output 2:
4 1 
0 1
Hint

Can you solve this problem by generating all the subsequences?

Approaches (2)
Using Recursion
  • 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.
Time Complexity

O(M), where M is the number of k-element subsequences of the array (M =  N! / ((N-K)! * K!)).

 

The number of k-element subsequences of the given array of length N is, M = N! / ((N-K)! * K!). As we are generating all these subsequences. Hence, the overall time complexity is O(M).

Space Complexity

O(K), where K is the length of the subsequences.

 

Extra space is required for the recursion stack. The maximum depth of recursion is O(K). Hence, the overall space complexity is O(K).

Code Solution
(100% EXP penalty)
Maximal AND Subsequences
Full screen
Console