1107. Slot AND Sum
A parcel depot has numSlots pigeonholes numbered 1 to numSlots, and every pigeonhole can hold at most two parcels. The array nums lists the sorting code of each parcel, and the depot has enough room for all of them. Holes may stay empty.
When a parcel with code c is put into pigeonhole k, the scanner awards c AND k points, where AND is the bitwise AND of the two numbers. The score of a layout is the sum of the points of all parcels. Return the highest score that any valid layout can reach.
Parcels with equal codes are still different parcels, and the order of nums does not matter for the answer.
Example 1
- Input:
- nums = [6,3,5,2,7], numSlots = 3
- Output:
- 11
- Explanation:
Put 5 into hole 1, 6 and 2 into hole 2, and 3 and 7 into hole 3: 1 + 2 + 2 + 3 + 3 = 11, and no layout does better.
Example 2
- Input:
- nums = [9,1,2], numSlots = 2
- Output:
- 4
- Explanation:
Parcels 9 and 1 share hole 1 (1 + 1 points) and parcel 2 goes to hole 2 for 2 points, giving 4.
Constraints
1 ≤ numSlots ≤ 10
1 ≤ nums.length ≤ 2 * numSlots
1 ≤ nums[i] ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(3^s * s)
- Space
- O(3^s)