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 slot1and[4, 6]into slot2is 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.length1 <= numSlots <= 91 <= n <= 2 * numSlots1 <= 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 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 slot1. - If
cnt = 2meaning two elements are selected, we pick one of them as the last element and put it in slot1. - If
cnt = 3meaning 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/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