Problem title
Difficulty
Avg time to solve

Ninja And Editor
Easy
20 mins
Encoded Letter
Moderate
25 mins
Tree Jumping
Hard
50 mins
Base Conversion
Easy
15 mins
Number of ones in the smallest repunit
Moderate
30 mins
Conversion
Easy
20 mins
Remove Comments
Moderate
15 mins
Last Substring In Lexicographical Order
Hard
45 mins
Minimum And Maximum
Easy
15 mins
Rectangles In N x N Board
Moderate
20 mins

Maximum AND Sum of Array

Difficulty: HARD
Contributed By

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.

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
Reset Code
Full screen
copy-code
Console