Maximize Total AND Across Limited Slots
Each number must be dropped into one of numSlots slots, and every slot holds at most two numbers. The score of a slot is the bitwise AND of the slot index with each number it holds; maximize the summed score.
Problem
Given an integer array nums and an integer numSlots (slots numbered 1..numSlots), place every number into some slot with at most two numbers per slot. The contribution of placing value v into slot i is (v AND i). Return the maximum possible sum of all contributions.
Input
An integer array nums and an integer numSlots with 2 * numSlots >= nums.length.
Output
An integer: the maximum total AND-sum.
Constraints
- 1 <= numSlots <= 9
- 1 <= nums.length <= 2 * numSlots
- 1 <= nums[i] <= 15
Examples
Example 1
Input
nums = [1,2,3,4,5,6], numSlots = 3
Output
9
An optimal assignment pairs numbers into slots 1,2,3 to total 9.
Example 2
Input
nums = [1,3,10,4,7,1], numSlots = 9
Output
24
Spread across high-index slots to maximize shared set bits.