Maximum AND Sum of Array

Published: Dec 22, 2022

Problem Description

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.

Constraints:

• n == nums.length
• 1 <= numSlots <= 9
• 1 <= n <= 2 * numSlots
• 1 <= nums[i] <= 15

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

Examples

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.

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

How to Solve

Solution

class MaximumANDSumOfArray {
public:
    int helper(vector<int> &nums, int numSlots, int i,
               vector<int> &memo, map<pair<int, vector<int>>, int> &seen) {
        if (i == nums.size()) { return 0; }
        if (seen.find({i, memo}) != seen.end()) {
            return seen[{i, memo}];
        }
        int result = INT_MIN;
        for (int j = 0; j < numSlots; ++j) {
            if (memo[j] < 2) {
                memo[j]++;
                int cur = (nums[i] & (j + 1)) + helper(nums, numSlots, i + 1, memo, seen);
                memo[j]--;
                result = max(result, cur);
            }
        }
        seen[{i, memo}] = result;
        return result;
    }

    int maximumANDSum(vector<int>& nums, int numSlots) {
        vector<int> memo(numSlots, 0);
        map<pair<int, vector<int>>, int> seen;
        return helper(nums, numSlots, 0, memo, seen);
    }
};

class MaximumANDSumOfArray:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        memo = [0 for _ in range(numSlots)]
        seen = {}

        def helper(i):
            if i == len(nums):
                return 0
            key = (i, ''.join([str(x) for x in memo]))
            if key in seen:
                return seen[key]
            result = float('-inf')
            for j in range(numSlots):
                if memo[j] < 2:
                    memo[j] += 1
                    cur = (nums[i] & (j + 1)) + helper(i + 1)
                    memo[j] -= 1
                    result = max(result, cur)
            seen[key] = result
            return result

        return helper(0)

Complexities

• Time: O()
• Space: O()