#2172

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum AND Sum of Array

Find the maximum AND sum by placing integers into limited slots using state transition dynamic programming efficiently.

array dynamic programming bit manipulation bitmask

Problem Statement

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. Each slot can hold at most two numbers from nums, and you need to assign all numbers to slots.

The AND sum of a placement is defined as the sum of each number AND its assigned slot number. Return the maximum possible AND sum after assigning all numbers optimally into the slots. For example, nums = [1,2,3,4,5,6] with numSlots = 3 yields a maximum AND sum of 9 with careful placement.

Examples

Example 1

Input: nums = [1,2,3,4,5,6], numSlots = 3

Output: 9

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

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.length
1 <= numSlots <= 9
1 <= n <= 2 * numSlots
1 <= nums[i] <= 15

Solution Approach

Use bitmask to track slot occupancy

Represent the occupancy of each slot as a digit in a ternary number to efficiently encode states in dynamic programming. This allows checking available slots and updating states in constant time per slot.

Apply state transition dynamic programming

Iterate through each number and all possible slot states. For each valid assignment, transition to a new state and update the maximum AND sum. This ensures all combinations are considered without recalculating redundant placements.

Optimize by pruning unreachable states

Skip states where a slot would exceed two numbers or where remaining numbers cannot fill available slots. This reduces computation and focuses on feasible assignments, leveraging the AND sum's additive property.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * 3^numSlots) due to enumerating states and transitions for each number. Space complexity is O(3^numSlots) to store DP states representing slot occupancy counts.

What Interviewers Usually Probe

Asks about handling at most two numbers per slot.
Hints at using dynamic programming with bitmasking.
Probes understanding of AND operation impact on sum maximization.

Common Pitfalls or Variants

Common pitfalls

Forgetting the two-number limit per slot, causing invalid states.
Not encoding slot occupancy efficiently, leading to exponential memory use.
Assuming greedy placement works, which may miss optimal AND sums.

Follow-up variants

Allowing variable slot capacities instead of fixed two per slot.
Maximizing OR sum instead of AND sum with similar slot constraints.
Limiting slot numbers further to increase DP state complexity.

FAQ

What is the key idea to solve Maximum AND Sum of Array?

Use state transition dynamic programming with bitmasking to track slot occupancy and maximize AND sum.

Can greedy approaches work for this problem?

Greedy methods usually fail because placing numbers sequentially may miss optimal AND sum combinations.

How do I encode slot occupancy for DP?

Use a ternary digit per slot to represent 0,1,2 numbers in a slot, forming a bitmask for state transitions.

Is there a memory-efficient way to handle DP states?

Yes, store only states that are reachable and prune states exceeding slot limits to save space.

Does this approach generalize to OR sum variants?

Yes, similar DP with bitmask works, but the sum calculation changes from AND to OR for each number and slot.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        n = len(nums)
        m = numSlots << 1
        f = [0] * (1 << m)
        for i in range(1 << m):
            cnt = i.bit_count()
            if cnt > n:
                continue
            for j in range(m):
                if i >> j & 1:
                    f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j // 2 + 1)))
        return max(f)

Continue Practicing

#2305 fair distribution of cookies #2035 partition array into two arrays to minimize sum difference #1994 the number of good subsets