Maximum AND Sum of Array

Hard
0/120
profile
Contributed by
18 upvotes
Asked in companies
HCL TechnologiesDeloitteWestern Digital

Problem statement

You are given an array of coins ‘COINS’ of length ‘N’ and there are ‘S’ number of slots numbered from 1 to S such that 2*S >= N.

You have to place all N coins into some slots so that no slot contains more than two coins. After placing the coins you will calculate the AND sum as the sum of all the values obtained by performing the bitwise AND operation between the slot number and the value of the coin placed in that slot number .

You have to find AND sum between the coins and the slots.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘S’ denoting the number of coins and the number of slots respectively.

The second line contains an integer array denoting the value of coins.
Example : 
Number of coins, N = 9
Number of slots, S = 8
Coins array, COINS = [14, 7, 9, 8, 2, 4, 1, 1, 1, 9]

One possible placement is to put coins having value:
[14, 7] into slot number 7, 
[9, 8] into slot number 8,
[2] into slot number 2,
[4] into slot number 4,
[1, 1] into slot number 3,
[1, 9] into slot number 1.

This gives the maximum AND sum of :
(14 AND 7) + (7 AND 7) + (9 AND 8) + (8 AND 8) + (2 AND 2) + (4 AND 3) + (11 AND 3) + (1 AND 9) = 6 + 7 + 8 + 8 + 2 + 4 + 3 + 1 + 1 = 40.
Note that slots number 5, 6 are empty which is permitted.
Output format : 
For each test case, output a single integer , AND sum between the coins and the slots.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10 
1 <= S <= 9
1 <= N <= 2 * S
1 <= COINS[i] <= 15

Time Limit: 5 sec
Sample Input 1 :
2
6 3
1 2 3 4 5 6
6 9
1 3 10 4 7 1
Sample Output 1 :
9
24
Explanation Of Sample Input 1 :
For test case 1 a possible placement of coins can be, 
[1, 4] into slot number 1, 
[2, 6] into slot number 2,
[3, 5] into slot number 3.

This gives the maximum AND sum of (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9.

For test case 2 a possible placement of coins can be,
[1, 1] into slot number 1, 
[3] into slot number 3,
[4] into slot number 4,
[7] into slot number 7.
[10] into slot number 9.

This gives the maximum AND sum of (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24.
Sample Input 2 :
2
7 4
10 5 3 6 11 8 8
11 8
8 13 3 15 3 15 2 15 5 7 6
Sample Output 2 :
16
60
Hint

Can you think of a dynamic programming solution to this problem?

Approaches (1)
Dynamic-Programming + BitMasking
  1. As the number of slots is very low this hints us to bitmasking where each mask will represent the state of all slots.
  2. We will create a mask of base 3, wherein each mask:
    • Each digit will represent a slot.
    • The value of each digit (0, 1, 2) will represent the number of coins in that slot.
  3. For this we will create a 2D DP in which :
    • The 1st dimension will represent each coin.
    • The 2nd dimension will represent the state of all slots for that coin.
  4. The transitions will be like this:
    • DP[coin][mask] = ( maximum of DP[coin][mask] and Dp[previous coin][previous state of kth slot in mask] ) + bitwise AND of ith coin and kth slot.
  5. The answer would be the maximum of all slots values in the last coin.


 

The steps are as follows : 

  1. Create a 2D DP array of size N x 3^S.
  2. Initialize the DP array as :
    • For each coin i from 0 to N-1
      • For each slot j from 0 to  S-1 set the DP[i][j] as bitwise AND of ith coin and mask of jth slot(3^j).
  3. To calculate the DP values :
    • For each coin i from 0 to N-1
      • For each mask from 0 to 3^S-1, we calculate the max value of this mask as :
        • For each slot k from 0 to S-1, first, we check if the kth slot is mask is valid i.e if the kth digit of the mask is not zero as we if we put a coin in the kth slot then the kth digit of mask increases by one but to calculate the maximum AND sum up to this coin we look for the value of kth digit of mask 1 less than the current value of kth digit of the mask.
        • If true then : DP[i][mask] = max(DP[i][mask], DP[i-1][mask-3^k]+coin[i] AND (k+1)).
  4. Create an ans variable to store answers from the maximum of all values in array DP[N-1].
Time Complexity

O( N * S * ( 3 ^ S ) ), where ‘N’ is the number of coins and ‘S’ is the number of slots.

 

Traversing the coins takes ~N, traversing on all masks takes ~( 3 ^ S ) and for each mask, we are traversing each slot that takes ~S. 

Hence the overall time complexity is O( N * S * ( 3 ^ S ) ).

Space Complexity

O( N * ( 3 ^ S ) ), where ‘N’ is the number of coins and ‘S’ is the number of slots.

 

Storing all the possible masks takes ~( 3 ^ S) and we maintain the mask for ‘N’ coins which takes ~N. 

Hence, the overall Space Complexity is O( N * ( 3 ^ S ) ).

Code Solution
(100% EXP penalty)
Maximum AND Sum of Array
Full screen
Console