LeetCode 2172 - Maximum AND Sum of Array

This problem asks us to distribute a set of integers into numbered slots in a way that maximizes a scoring function based on bitwise AND operations.

leetcodehardarraydynamic-programmingbit-manipulationbitmask

LeetCode Problem 2172

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Bitmask

Solution

LeetCode 2172 - Maximum AND Sum of Array

Problem Understanding

This problem asks us to distribute a set of integers into numbered slots in a way that maximizes a scoring function based on bitwise AND operations.

We are given:

  • An integer array nums
  • A number of slots, numSlots
  • Each slot is numbered from 1 to numSlots
  • Each slot can contain at most two numbers

For every number placed into a slot, we gain a score equal to:

number AND slot_number

The final score is the sum of all these values across every placed number.

The goal is to determine the maximum possible AND sum.

The important detail is that the slot number itself participates in the AND operation. This means that different numbers benefit differently depending on which slot they are assigned to.

For example:

5 AND 3 = 1
5 AND 5 = 5
5 AND 2 = 0

So the placement strategy matters significantly.

The constraints are extremely important:

  • numSlots <= 9
  • Each slot holds at most two numbers
  • Therefore the total capacity is at most 18
  • nums.length <= 18

Although 18 is small, the number of possible assignments is still enormous if explored naively. This strongly suggests that exponential algorithms with memoization or bitmask dynamic programming are intended.

The values in nums are also small:

1 <= nums[i] <= 15

However, the actual values are less important than the assignment structure.

Several edge cases are worth noting immediately:

  • Some slots may remain empty
  • Multiple numbers may have identical values
  • numSlots can be larger than necessary
  • A number may produce zero contribution in some slots
  • Since each slot holds at most two numbers, capacity management is critical

The problem guarantees:

2 * numSlots >= n

so there is always enough total capacity to place every number.

Approaches

Brute Force Approach

A straightforward solution would try every possible placement of every number into every slot.

For each number, we could:

  • Try placing it into slot 1
  • Try placing it into slot 2
  • Continue until slot numSlots
  • Skip slots that already contain two numbers

We would recursively generate all valid assignments and compute the total AND sum for each configuration.

This approach is correct because it explores every legal arrangement, so the maximum found must be optimal.

Unfortunately, it is far too slow.

Each number can potentially go into many slots, producing roughly:

O(numSlots^n)

states in the worst case.

With:

n <= 18
numSlots <= 9

this becomes astronomically large.

Key Insight

The critical observation is that the state of the problem can be represented compactly using bitmasks.

Since each slot can hold two numbers, we can think of the problem as having:

2 * numSlots

individual positions.

For example, if:

numSlots = 3

then we have six assignable positions:

slot 1 -> positions 0,1
slot 2 -> positions 2,3
slot 3 -> positions 4,5

Now the problem becomes:

  • Assign each number to one unused position
  • Each pair of positions corresponds to one slot

This transforms the problem into a classic bitmask DP problem.

We define:

mask = which positions are already occupied

From the number of bits set in mask, we know:

  • How many numbers have already been placed
  • Which number from nums we are currently assigning

This avoids storing explicit slot contents.

The number of possible masks is:

2^(2 * numSlots)

At maximum:

2^18 = 262144

which is manageable.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(numSlots^n) O(n) Tries every possible placement recursively
Optimal Bitmask DP O((2^(2_numSlots)) * (2_numSlots)) O(2^(2*numSlots)) Uses DP over assignment states

Algorithm Walkthrough

Step 1: Represent slot capacity as positions

Each slot can contain two numbers.

Instead of tracking slot contents directly, create:

2 * numSlots

virtual positions.

Example:

slot 1 -> positions 0 and 1
slot 2 -> positions 2 and 3
slot 3 -> positions 4 and 5

The slot number for position p is:

(p // 2) + 1

This representation makes capacity handling extremely simple.

Step 2: Define the DP state

We use a bitmask:

mask

where:

  • Bit i is 1 if position i is occupied
  • Bit i is 0 if position i is free

The number of set bits tells us how many numbers have already been assigned.

If:

used = popcount(mask)

then the next number to place is:

nums[used]

Step 3: Define the transition

For every unused position:

  • Determine its slot number
  • Compute contribution:
nums[used] & slot_number
  • Create the new mask with that position occupied
  • Recursively compute the best future score

Transition formula:

dp(mask) =
max(
    (nums[idx] & slot) + dp(next_mask)
)

Step 4: Base case

If all numbers have been assigned:

idx == len(nums)

then no further score can be added.

Return:

0

Step 5: Memoize results

Many masks are revisited repeatedly.

Store computed answers in a memoization cache so each mask is solved only once.

This reduces exponential recomputation dramatically.

Why it works

The DP works because every valid assignment corresponds to exactly one sequence of occupied positions in the mask. The mask fully captures the state needed to continue the optimization process.

At every step, the algorithm considers all valid placements for the next number and chooses the one that maximizes:

current contribution + optimal future contribution

Since all future states are solved optimally through recursion and memoization, the final answer is globally optimal.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        total_positions = 2 * numSlots
        n = len(nums)

        @lru_cache(None)
        def dp(mask: int) -> int:
            idx = mask.bit_count()

            if idx == n:
                return 0

            best = 0

            for pos in range(total_positions):
                if (mask & (1 << pos)) == 0:
                    slot = (pos // 2) + 1

                    candidate = (
                        (nums[idx] & slot)
                        + dp(mask | (1 << pos))
                    )

                    best = max(best, candidate)

            return best

        return dp(0)

The implementation begins by converting the slot system into virtual positions. Since each slot can contain two numbers, there are exactly 2 * numSlots assignable positions.

The recursive function dp(mask) represents the maximum achievable AND sum after filling the positions represented by mask.

The expression:

mask.bit_count()

tells us how many numbers have already been placed. That directly determines which number from nums should be assigned next.

For every unused position:

if (mask & (1 << pos)) == 0

we compute its slot number using:

slot = (pos // 2) + 1

Then we evaluate the contribution from assigning the current number to that slot.

Memoization is critical. Without caching, identical masks would be recomputed repeatedly, leading to exponential blowup.

The recursion starts from:

dp(0)

which represents the empty assignment state.

Go Solution

func maximumANDSum(nums []int, numSlots int) int {
	totalPositions := 2 * numSlots
	n := len(nums)

	memo := make(map[int]int)

	var bitCount func(int) int
	bitCount = func(x int) int {
		count := 0
		for x > 0 {
			count += x & 1
			x >>= 1
		}
		return count
	}

	var dp func(int) int

	dp = func(mask int) int {
		if val, exists := memo[mask]; exists {
			return val
		}

		idx := bitCount(mask)

		if idx == n {
			return 0
		}

		best := 0

		for pos := 0; pos < totalPositions; pos++ {
			if (mask & (1 << pos)) == 0 {
				slot := (pos / 2) + 1

				candidate := (nums[idx] & slot) + dp(mask|(1<<pos))

				if candidate > best {
					best = candidate
				}
			}
		}

		memo[mask] = best
		return best
	}

	return dp(0)
}

The Go implementation follows the same logic as the Python version.

Go does not provide a built in bit_count() method for integers in the same way Python does, so we implement a helper function to count set bits manually.

The memoization structure is implemented using:

map[int]int

where the key is the bitmask state and the value is the optimal score from that state onward.

Since the maximum score is small and the constraints are limited, standard int values are completely safe from overflow.

Worked Examples

Example 1

Input:

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

We have:

positions = 6

Mapping:

Position Slot
0 1
1 1
2 2
3 2
4 3
5 3

Initial state:

Mask Assigned Numbers Current Number
000000 none 1

Try placing 1:

Position Slot Contribution
0 1 1 & 1 = 1
1 1 1
2 2 0
3 2 0
4 3 1
5 3 1

Suppose we choose position 0.

New state:

Mask Assigned Numbers Current Number
000001 [1] 2

Now try placing 2:

Position Slot Contribution
1 1 0
2 2 2
3 2 2
4 3 2
5 3 2

The DP continues recursively until all numbers are assigned.

Eventually the optimal placement becomes:

Slot Numbers
1 [1,4]
2 [2,6]
3 [3,5]

Total:

1 + 0 + 2 + 2 + 3 + 1 = 9

Example 2

Input:

nums = [1,3,10,4,7,1]
numSlots = 9

There are:

18 positions

Many slots remain unused.

The algorithm explores assignments and discovers:

Slot Numbers Contribution
1 [1,1] 1 + 1
3 [3] 3
4 [4] 4
7 [7] 7
9 [10] 8

Total:

24

The DP naturally handles unused slots because there is no requirement to fill every position.

Complexity Analysis

Measure Complexity Explanation
Time O((2^(2_numSlots)) * (2_numSlots)) Every mask tries all positions
Space O(2^(2*numSlots)) Memoization stores one value per mask

The maximum number of positions is:

2 * 9 = 18

so the number of masks is:

2^18 = 262144

For each mask, we may iterate through up to 18 positions.

This is efficient enough for the problem constraints.

Test Cases

sol = Solution()

# Provided example 1
assert sol.maximumANDSum([1,2,3,4,5,6], 3) == 9

# Provided example 2
assert sol.maximumANDSum([1,3,10,4,7,1], 9) == 24

# Single number, single slot
assert sol.maximumANDSum([1], 1) == 1

# Two numbers, one slot
assert sol.maximumANDSum([1,1], 1) == 2

# Numbers producing zero AND in some slots
assert sol.maximumANDSum([8,8], 1) == 0

# Exact full capacity
assert sol.maximumANDSum([1,2,3,4], 2) == 5

# Large slot count with few numbers
assert sol.maximumANDSum([15,15], 9) == 24

# Repeated numbers
assert sol.maximumANDSum([7,7,7,7], 2) == 6

# Minimum constraints
assert sol.maximumANDSum([1], 1) == 1

# Stress style case near maximum size
assert sol.maximumANDSum(
    [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,2,3],
    9
) >= 0

Test Summary

Test Why
[1,2,3,4,5,6], 3 Validates official example
[1,3,10,4,7,1], 9 Validates sparse slot usage
[1], 1 Minimum input size
[1,1], 1 Single slot with full capacity
[8,8], 1 AND results can be zero
[1,2,3,4], 2 Exact capacity utilization
[15,15], 9 Best placement among many slots
[7,7,7,7], 2 Repeated values
Maximum sized array Stress test for DP state count

Edge Cases

One important edge case occurs when many slots are unused. Since the problem only restricts maximum capacity and does not require every slot to contain numbers, the optimal solution may intentionally leave many slots empty. The DP handles this naturally because it only assigns positions for existing numbers and never forces full occupancy.

Another subtle case occurs when certain assignments contribute zero. For example:

8 AND 1 = 0

A greedy algorithm might incorrectly assume every placement should maximize immediate contribution. However, sometimes placing a number into a lower scoring slot allows another number to achieve a much larger score later. The DP avoids this issue by exploring all possibilities.

A third important edge case involves repeated numbers. If many values are identical, naive recursive implementations may redundantly recompute equivalent states many times. Memoization prevents this by caching results for every bitmask state, ensuring each configuration is solved only once.

Finally, the maximum constraint size is itself an important edge case. With up to 18 assignments, brute force recursion becomes infeasible. The bitmask DP succeeds because the state space is capped at roughly 262144 masks, which is manageable within typical LeetCode limits.