1230. Maximum AND Sum of Array

HardDynamic ProgrammingBitmask DP

Given nums and numSlots numbered 1 to numSlots, place every number into a slot with at most two numbers per slot. The score is the sum over placed numbers of (number AND its slot number). Return the maximum possible score. The input is JSON {nums, numSlots}.

Input: JSON {nums, numSlots}.

Output: Integer — the maximum AND sum.

Examples

Example 1 
Input: {"nums":[1,2,3,4,5,6],"numSlots":3}
Output: 9
Explanation: An optimal placement scores 9.
Example 2 
Input: {"nums":[1,3,10,4,7,1],"numSlots":9}
Output: 24
Explanation: Optimal placement scores 24.
Example 3 
Input: {"nums":[1],"numSlots":1}
Output: 1
Explanation: 1 AND 1 = 1.

Constraints

Asked by

Google
Solve this problem in the editor →