Published: Dec 22, 2022

## Problem Description

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 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.Constraints:

`n == nums.length`

`1 <= numSlots <= 9`

`1 <= n <= 2 * numSlots`

`1 <= nums[i] <= 15`

## Examples

```
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.
```

```
Exmaple 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.
```

## How to Solve

## Solution

```
class MaximumANDSumOfArray {
public:
int helper(vector<int> &nums, int numSlots, int i,
vector<int> &memo, map<pair<int, vector<int>>, int> &seen) {
if (i == nums.size()) { return 0; }
if (seen.find({i, memo}) != seen.end()) {
return seen[{i, memo}];
}
int result = INT_MIN;
for (int j = 0; j < numSlots; ++j) {
if (memo[j] < 2) {
memo[j]++;
int cur = (nums[i] & (j + 1)) + helper(nums, numSlots, i + 1, memo, seen);
memo[j]--;
result = max(result, cur);
}
}
seen[{i, memo}] = result;
return result;
}
int maximumANDSum(vector<int>& nums, int numSlots) {
vector<int> memo(numSlots, 0);
map<pair<int, vector<int>>, int> seen;
return helper(nums, numSlots, 0, memo, seen);
}
};
```

```
```

```
```

```
class MaximumANDSumOfArray:
def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
memo = [0 for _ in range(numSlots)]
seen = {}
def helper(i):
if i == len(nums):
return 0
key = (i, ''.join([str(x) for x in memo]))
if key in seen:
return seen[key]
result = float('-inf')
for j in range(numSlots):
if memo[j] < 2:
memo[j] += 1
cur = (nums[i] & (j + 1)) + helper(i + 1)
memo[j] -= 1
result = max(result, cur)
seen[key] = result
return result
return helper(0)
```

```
```

## Complexities

- Time:
`O()`

- Space:
`O()`