Maximum AND Sum of Array
You are given an integer array nums of length n and an integer numSlots such that 2 * numSlots >= n. There are numSlots slots numbered from 1 to numSlots.
You have to place all n integers into the slots such that each slot contains at most two numbers. The AND sum of a given placement is the sum of the bitwise AND of every number with its respective slot number.
- For example, the AND sum of placing the numbers
[1, 3]into slot1and[4, 6]into slot2is equal to(1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4.
Return the maximum possible AND sum of nums given numSlots slots.
Example 1
Input
nums = [1,2,3,4,5,6], numSlots = 3Output
9One possible optimal placement is [1, 4] into slot 1, [2, 6] into slot 2, and [3, 5] into slot 3, giving an AND sum of 9.
Example 2
Input
nums = [1,3,10,4,7,1], numSlots = 9Output
24One possible optimal placement is [1, 1] into slot 1, [3] into slot 3, [4] into slot 4, [7] into slot 7, and [10] into slot 9, giving an AND sum of 24 while some slots remain empty.
Constraints
- n == nums.length
- 1 <= numSlots <= 9
- 1 <= n <= 2 * numSlots
- 1 <= nums[i] <= 15