Maximum AND Sum of Array
01 · Problem
You are given an integer array nums of length n and an integer numSlots with 2 * numSlots >= n. There are numSlots slots numbered 1 to numSlots.
Place every number of nums into some slot so that each slot holds at most two numbers (slots may stay empty). The AND sum of a placement is the sum over all numbers of num AND slotNumber, where slotNumber is the slot that number was placed in.
Return the maximum AND sum that can be achieved.
02 · Examples
nums = [1,2,3,4,5,6], numSlots = 3
9
Place 1 and 4 in slot 1, 2 and 6 in slot 2, 3 and 5 in slot 3. The AND sum is (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9.
nums = [1,3,10,4,7,1], numSlots = 9
24
Place both 1s in slot 1, 3 in slot 3, 4 in slot 4, 7 in slot 7 and 10 in slot 8. The AND sum is 1 + 1 + 3 + 4 + 7 + 8 = 24. Slots 2, 5, 6 and 9 stay empty.
03 · Constraints
- 01n == nums.length
- 021 <= numSlots <= 9
- 031 <= n <= 2 * numSlots
- 041 <= nums[i] <= 15
04 · Optimal complexity
- Time
- O(numSlots * 4^numSlots)
- Space
- O(4^numSlots)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.