Watch 6 video solutions for Maximum AND Sum of Array, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Vivek Gupta has 3,277 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums of length n and an integer numSlots such that 2 * numSlots >= n. There are numSlots slots numbered from 1 to numSlots.
You have to place all n integers into the slots such that each slot contains at most two numbers. The AND sum of a given placement is the sum of the bitwise AND of every number with its respective slot number.
[1, 3] into slot 1 and [4, 6] into slot 2 is equal to (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4.Return the maximum possible AND sum of nums given numSlots slots.
Example 1:
Input: nums = [1,2,3,4,5,6], numSlots = 3 Output: 9 Explanation: One possible placement is [1, 4] into slot 1, [2, 6] into slot 2, and [3, 5] into slot 3. This gives the maximum AND sum of (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.
Example 2:
Input: nums = [1,3,10,4,7,1], numSlots = 9 Output: 24 Explanation: One possible placement is [1, 1] into slot 1, [3] into slot 3, [4] into slot 4, [7] into slot 7, and [10] into slot 9. This gives the maximum AND sum of (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24. Note that slots 2, 5, 6, and 8 are empty which is permitted.
Constraints:
n == nums.length1 <= numSlots <= 91 <= n <= 2 * numSlots1 <= nums[i] <= 15Problem Overview: You are given an array nums and numSlots slots where each slot can hold at most two numbers. Placing a number x in slot i contributes x & i to the score. The goal is to assign every number to a slot so the total AND sum is maximized.
Approach 1: Backtracking Assignment (Exponential Time)
This method tries every possible assignment of numbers to slots. Maintain a counter for how many numbers each slot currently holds (maximum two). Recursively place the next number into any slot with available capacity and accumulate the contribution nums[i] & slotIndex. The algorithm explores the full search tree of placements and tracks the best score found.
The time complexity is roughly O((numSlots^n)) in the worst case because each number may be placed in multiple slots. Space complexity is O(numSlots) for recursion state. This approach is useful for understanding the problem structure and verifying small inputs, but it becomes slow as the search space grows.
Approach 2: Dynamic Programming with Bitmask (Optimal)
The key observation is that each slot can hold exactly two positions. Instead of tracking slots directly, treat the problem as assigning numbers to 2 × numSlots positions. Use a bitmask where each bit represents whether a position is already filled. If the mask has k bits set, you are assigning the k-th number in nums.
For every unused position in the mask, compute the slot index as (position / 2) + 1 and add nums[k] & slot. Update the DP state for the new mask. This converts the exponential assignment problem into a manageable state transition over bitmasks.
The time complexity becomes O((2 × numSlots) × 2^(2 × numSlots)) because each mask tries filling the remaining positions. Space complexity is O(2^(2 × numSlots)) for the DP table. Since numSlots ≤ 9, the state space is small enough to compute efficiently.
This approach heavily relies on bitmask state compression and dynamic programming transitions over subsets. The input structure itself comes from a simple array, but the optimization comes from representing assignments compactly with bits.
Recommended for interviews: Start by explaining the brute-force backtracking approach to show you understand the assignment constraints. Then transition to the bitmask DP optimization. Interviewers typically expect the DP with bitmask solution because it reduces the exponential branching into a structured state space and demonstrates strong subset-DP skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Assignment | O(numSlots^n) | O(numSlots) | Good for understanding the placement logic or solving very small inputs |
| Dynamic Programming with Bitmask | O((2·numSlots) · 2^(2·numSlots)) | O(2^(2·numSlots)) | Optimal approach for the general case where numSlots ≤ 9 |