Formatted question description: https://leetcode.ca/all/2172.html

# 2172. Maximum AND Sum of Array (Hard)

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.

- For example, the
**AND sum**of placing the numbers`[1, 3]`

into slotand`1`

`[4, 6]`

into slotis equal to`2`

`(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 = 3Output:9Explanation:One possible placement is [1, 4] into slot1, [2, 6] into slot2, and [3, 5] into slot3. This gives the maximum AND sum of (1 AND1) + (4 AND1) + (2 AND2) + (6 AND2) + (3 AND3) + (5 AND3) = 1 + 0 + 2 + 2 + 3 + 1 = 9.

**Example 2:**

Input:nums = [1,3,10,4,7,1], numSlots = 9Output:24Explanation:One possible placement is [1, 1] into slot1, [3] into slot3, [4] into slot4, [7] into slot7, and [10] into slot9. This gives the maximum AND sum of (1 AND1) + (1 AND1) + (3 AND3) + (4 AND4) + (7 AND7) + (10 AND9) = 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`

**Similar Questions**:

## Solution 1. Bitmask DP

**Intuition**:

If we permuate the numbers and assign them to the slots sequentially (`A[0]`

and `A[1]`

into slot `1`

, `A[2]`

and `A[3]`

into slot `2`

, …), we need to go over at most `18!`

permutations which will result in TLE.

It’s wasting computation because it computes the same subproblem over and over again. For example, assume we assigned `A[0] to A[9]`

10 elements to the first `5`

slots. For the first element in slot `6`

, we have `A[10] to A[17]`

8 options. But no matter which one we choose, the best arrangment for the first 10 elements is fixed. Instead of computing it `8`

times, we can just compute it once and reuse it later. This leads to a DP solution.

The DP idea is that we use bitmask `m`

to represent which elements are selected, and try picking each one of them as the last element and assign it to `(bitCount(m) + 1) / 2`

-th slot. The state transition is `dp[m - (1 << i)] -> dp[m]`

where `m`

’s `i`

-th bit is `1`

.

**Algorithm**:

Append `0`

s to make sure the length of `A`

is `2 * numSlots`

.

Let `dp[m]`

be the maximum score given a bitmask `m`

representing the selected numbers. The final answer is `dp[(1 << N) - 1]`

.

Assume `m`

’s `i`

-th bit is `1`

, we have the following formula:

```
dp[m] = max( dp[m - (1 << i)] + (slotNumber & A[i]) | m's i-th bit is 1 )
where slotNumber = (cnt + 1) / 2 and cnt = bitCount(m)
```

The key is that we always make this picked `A[i]`

as the last element of all elements in `m`

and assign it to `slotNumber`

-th slot, and `slotNumber`

is a constant given `m`

.

**Why slotNumber = (cnt + 1) / 2?**

- If
`cnt = 1`

, we put this first element at slot`1`

. - If
`cnt = 2`

meaning two elements are selected, we pick one of them as the last element and put it in slot`1`

. - If
`cnt = 3`

meaning three elements are seledted, we pick one of them as the last element and put it in slot`2`

. - ans so on…

So the `cnt`

to `slotNumber`

mapping is `1 or 2 -> 1`

, `3 or 4 -> 2`

, … i.e. `slotNumber = (cnt + 1) / 2`

.

**Example of State Transition**:

Assume `m = 1101`

, we’ll assign `A[i]`

to slot `(bitCount(m) + 1) / 2 = (3 + 1) / 2 = 2`

:

- If
`i = 0`

,`dp[1101] = dp[1100] + (2 & A[0])`

- If
`i = 2`

,`dp[1101] = dp[1001] + (2 & A[2])`

- If
`i = 3`

,`dp[1101] = dp[0101] + (2 & A[3])`

.

```
// OJ: https://leetcode.com/problems/maximum-and-sum-of-array/
// Time: O(2^(2*numSlots) * numSlots)
// Space: O(2^(2*numSlots))
class Solution {
public:
int maximumANDSum(vector<int>& A, int numSlots) {
A.resize(2 * numSlots); // append 0s to make sure the length of `A` is `2 * numSlots`
int N = A.size();
vector<int> dp(1 << N);
for (int m = 1; m < 1 << N; ++m) {
int cnt = __builtin_popcount(m), slot = (cnt + 1) / 2;
for (int i = 0; i < N; ++i) {
if (m >> i & 1) { // we assign A[i] to `slot`-th slot
dp[m] = max(dp[m], dp[m ^ (1 << i)] + (slot & A[i]));
}
}
}
return dp[(1 << N) - 1];
}
};
```

## Discuss

https://leetcode.com/problems/maximum-and-sum-of-array/discuss/1766743