##### Welcome to Subscribe On Youtube

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

Similar Questions:

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 0s 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];
}
};

• # 2172. Maximum AND Sum of Array
# https://leetcode.com/problems/maximum-and-sum-of-array/

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

@cache
def go(index, slots):
if index == n:
return 0

res = 0

for slot in range(numSlots):
if slots & (1 << (slot * 2)) > 0 and slots & (1 << (slot * 2 + 1)) > 0: continue

y = nums[index] & (slot + 1)

if slots & (1 << (slot * 2)) == 0:
res = max(res, y + go(index + 1, slots ^ (1 << (slot * 2))))
else:
res = max(res, y + go(index + 1, slots ^ (1 << (slot * 2 + 1))))

return res

return go(0, 0)


• class Solution {
public int maximumANDSum(int[] nums, int numSlots) {
int n = nums.length;
int m = numSlots << 1;
int[] f = new int[1 << m];
int ans = 0;
for (int i = 0; i < 1 << m; ++i) {
int cnt = Integer.bitCount(i);
if (cnt > n) {
continue;
}
for (int j = 0; j < m; ++j) {
if ((i >> j & 1) == 1) {
f[i] = Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j / 2 + 1)));
}
}
ans = Math.max(ans, f[i]);
}
return ans;
}
}

• func maximumANDSum(nums []int, numSlots int) (ans int) {
n := len(nums)
m := numSlots << 1
f := make([]int, 1<<m)
for i := range f {
cnt := bits.OnesCount(uint(i))
if cnt > n {
continue
}
for j := 0; j < m; j++ {
if i>>j&1 == 1 {
f[i] = max(f[i], f[i^(1<<j)]+(nums[cnt-1]&(j/2+1)))
}
}
ans = max(ans, f[i])
}
return
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

• function maximumANDSum(nums: number[], numSlots: number): number {
const n = nums.length;
const m = numSlots << 1;
const f: number[] = new Array(1 << m).fill(0);
for (let i = 0; i < 1 << m; ++i) {
const cnt = i
.toString(2)
.split('')
.filter(c => c === '1').length;
if (cnt > n) {
continue;
}
for (let j = 0; j < m; ++j) {
if (((i >> j) & 1) === 1) {
f[i] = Math.max(
f[i],
f[i ^ (1 << j)] + (nums[cnt - 1] & ((j >> 1) + 1)),
);
}
}
}
return Math.max(...f);
}



## Discuss

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