Lockers and Bitwise AND

Hard

A changing room has lockers lockers numbered from 1 to lockers, and each holds at most two items. Every item carries a number, given in the array items. All items must be stored. An item with number v placed in locker s scores v AND s points (bitwise AND). The score of a placement is the sum over all items. Return the highest score you can reach. Lockers may stay empty.

Example 1

items=[3, 5, 6, 1], lockers=2 → 6

Put 3 and 6 into locker 2: (3 AND 2) + (6 AND 2) = 2 + 2 = 4. Put 5 and 1 into locker 1: 1 + 1 = 2. The total is 6.

Example 2

items=[4], lockers=5 → 4

Item 4 can go into locker 4 or 5: 4 AND 4 = 4 AND 5 = 4. Empty lockers are fine.

Example 3

items=[7, 7, 7], lockers=3 → 8

Two 7s in locker 3 give 3 each, and the third one in locker 2 gives 2, for 8 in total.

Constraints

1 ≤ lockers ≤ 9
1 ≤ len(items) ≤ 2 · lockers
1 ≤ items[i] ≤ 15

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming Bitmask

Similar problems

Settle Up in the Fewest Transfers Hard Two Groups With the Same Average Hard Assembling Fragments Hard Square-Sum Chains Hard Smallest Team With Every Skill Hard

Input

items=[3, 5, 6, 1], lockers=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.