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.
This approach explores all possible placements of the numbers into the slots and calculates the AND sum for each configuration. It keeps track of the maximum AND sum encountered. The constraints allow this brute-force-like method to be feasible given that n is small.
The function max_and_sum uses a backtracking approach to find the maximum AND sum. The helper function backtrack attempts to place each number from nums into available slots recursively, keeping track of the maximum AND combination.
Time Complexity: O(Sn), where S is the number of slots. In the worst case, we explore all permutations.
Space Complexity: O(n), due to the recursion stack.
This approach employs dynamic programming and bit masking to efficiently calculate the maximum AND sum. Each state in the DP table represents a combination of slots filled and their respective configurations.
This Java solution utilizes a dynamic programming table where each state is denoted by a bit mask representing numbers used and slots filled. It optimally calculates the maximum AND sum using bottom-up DP.
Java
JavaScript
Time Complexity: O(2n * n * S), where S is the number of slots.
Space Complexity: O(2n * S), for the DP table.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(Sn), where S is the number of slots. In the worst case, we explore all permutations. |
| Dynamic Programming with Bit Mask | Time Complexity: O(2n * n * S), where S is the number of slots. |
| Default Approach | — |
| 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 |
Hardest on Leetcode ?? | One Problem - Four Solutions | Leetcode Weekly Episode 4 | Leetcode 2172 • Vivek Gupta • 3,277 views views
Watch 5 more video solutions →Practice Maximum AND Sum of Array with our built-in code editor and test cases.
Practice on FleetCode