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

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

Each slot can hold at most two numbers, and the number of slots is small (≤15). We can use bitmask dynamic programming to represent the assignment of numbers to slots. For each state, we try to assign the next number to any slot that is not full, and recursively compute the maximum AND sum.

Approach

Use a DP array where the state is a bitmask representing the assignment of numbers to slots (2 bits per slot).
For each state, try to assign the next number to any slot that is not full (less than 2 numbers in the slot).
For each assignment, update the DP state and add the AND value to the sum.
The answer is the maximum sum for the full assignment.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maximumANDSum(vector<int>& nums, int numSlots) {\n        int n = nums.size();\n        int m = numSlots;\n        int maxMask = pow(3, m);\n        vector<int> dp(maxMask, 0);\n        for (int mask = 0; mask < maxMask; ++mask) {\n            int cnt = 0, tmp = mask;\n            for (int i = 0; i < m; ++i) {\n                cnt += tmp % 3;\n                tmp /= 3;\n            }\n            if (cnt >= n) continue;\n            for (int i = 0, t = mask; i < m; ++i, t /= 3) {\n                if (t % 3 < 2) {\n                    int nmask = mask + pow(3, i);\n                    dp[nmask] = max(dp[nmask], dp[mask] + (nums[cnt] & (i+1)));\n                }\n            }\n        }\n        return *max_element(dp.begin(), dp.end());\n    }\n};","lang":"cpp"},{"language":"Go","code":"func maximumANDSum(nums []int, numSlots int) int {\n    n, m := len(nums), numSlots\n    maxMask := 1\n    for i := 0; i < m; i++ {\n        maxMask *= 3\n    }\n    dp := make([]int, maxMask)\n    for mask := 0; mask < maxMask; mask++ {\n        cnt, tmp := 0, mask\n        for i := 0; i < m; i++ {\n            cnt += tmp % 3\n            tmp /= 3\n        }\n        if cnt >= n {\n            continue\n        }\n        for i, t := 0, mask; i < m; i, t = i+1, t/3 {\n            if t%3 < 2 {\n                nmask := mask + pow3(i)\n                if dp[nmask] < dp[mask]+(nums[cnt]&(i+1)) {\n                    dp[nmask] = dp[mask] + (nums[cnt] & (i+1))\n                }\n            }\n        }\n    }\n    ans := 0\n    for _, v := range dp {\n        if v > ans {\n            ans = v\n        }\n    }\n    return ans\n}\nfunc pow3(x int) int {\n    res := 1\n    for i := 0; i < x; i++ {\n        res *= 3\n    }\n    return res\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int maximumANDSum(int[] nums, int numSlots) {\n        int n = nums.length, m = numSlots;\n        int maxMask = (int)Math.pow(3, m);\n        int[] dp = new int[maxMask];\n        for (int mask = 0; mask < maxMask; ++mask) {\n            int cnt = 0, tmp = mask;\n            for (int i = 0; i < m; ++i) {\n                cnt += tmp % 3;\n                tmp /= 3;\n            }\n            if (cnt >= n) continue;\n            for (int i = 0, t = mask; i < m; ++i, t /= 3) {\n                if (t % 3 < 2) {\n                    int n

Related Tags