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:

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

All Problems

All Solutions