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 slot1
and[4, 6]
into slot2
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:
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 ith 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 slot1
.  If
cnt = 2
meaning two elements are selected, we pick one of them as the last element and put it in slot1
.  If
cnt = 3
meaning three elements are seledted, we pick one of them as the last element and put it in slot2
.  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/maximumandsumofarray/ // 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/maximumandsumofarray/ 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[cnt1]&(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/maximumandsumofarray/discuss/1766743