Maximum AND Sum of Array

Problem

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 possibleAND sum of _nums givennumSlots slots.

Examples

Example 1

1
2
3
4


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

1
2
3
4
5


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        int n = nums.size();
        int m = numSlots;
        int maxMask = pow(3, m);
        vector<int> dp(maxMask, 0);
        for (int mask = 0; mask < maxMask; ++mask) {
            int cnt = 0, tmp = mask;
            for (int i = 0; i < m; ++i) {
                cnt += tmp % 3;
                tmp /= 3;
            }
            if (cnt >= n) continue;
            for (int i = 0, t = mask; i < m; ++i, t /= 3) {
                if (t % 3 < 2) {
                    int nmask = mask + pow(3, i);
                    dp[nmask] = max(dp[nmask], dp[mask] + (nums[cnt] & (i+1)));
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


func maximumANDSum(nums []int, numSlots int) int {
    n, m := len(nums), numSlots
    maxMask := 1
    for i := 0; i < m; i++ {
        maxMask *= 3
    }
    dp := make([]int, maxMask)
    for mask := 0; mask < maxMask; mask++ {
        cnt, tmp := 0, mask
        for i := 0; i < m; i++ {
            cnt += tmp % 3
            tmp /= 3
        }
        if cnt >= n {
            continue
        }
        for i, t := 0, mask; i < m; i, t = i+1, t/3 {
            if t%3 < 2 {
                nmask := mask + pow3(i)
                if dp[nmask] < dp[mask]+(nums[cnt]&(i+1)) {
                    dp[nmask] = dp[mask] + (nums[cnt] & (i+1))
                }
            }
        }
    }
    ans := 0
    for _, v := range dp {
        if v > ans {
            ans = v
        }
    }
    return ans
}
func pow3(x int) int {
    res := 1
    for i := 0; i < x; i++ {
        res *= 3
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        int n = nums.length, m = numSlots;
        int maxMask = (int)Math.pow(3, m);
        int[] dp = new int[maxMask];
        for (int mask = 0; mask < maxMask; ++mask) {
            int cnt = 0, tmp = mask;
            for (int i = 0; i < m; ++i) {
                cnt += tmp % 3;
                tmp /= 3;
            }
            if (cnt >= n) continue;
            for (int i = 0, t = mask; i < m; ++i, t /= 3) {
                if (t % 3 < 2) {
                    int nmask = mask + (int)Math.pow(3, i);
                    dp[nmask] = Math.max(dp[nmask], dp[mask] + (nums[cnt] & (i+1)));
                }
            }
        }
        int ans = 0;
        for (int v : dp) ans = Math.max(ans, v);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    fun maximumANDSum(nums: IntArray, numSlots: Int): Int {
        val n = nums.size
        val m = numSlots
        val maxMask = Math.pow(3.0, m.toDouble()).toInt()
        val dp = IntArray(maxMask)
        for (mask in 0 until maxMask) {
            var cnt = 0
            var tmp = mask
            for (i in 0 until m) {
                cnt += tmp % 3
                tmp /= 3
            }
            if (cnt >= n) continue
            var t = mask
            for (i in 0 until m) {
                if (t % 3 < 2) {
                    val nmask = mask + Math.pow(3.0, i.toDouble()).toInt()
                    dp[nmask] = maxOf(dp[nmask], dp[mask] + (nums[cnt] and (i+1)))
                }
                t /= 3
            }
        }
        return dp.maxOrNull() ?: 0
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def maximumANDSum(self, nums: list[int], numSlots: int) -> int:
        from functools import lru_cache
        n = len(nums)
        @lru_cache(None)
        def dp(i: int, mask: int) -> int:
            if i == n:
                return 0
            ans = 0
            for slot in range(numSlots):
                cnt = (mask // (3 ** slot)) % 3
                if cnt < 2:
                    nmask = mask + 3 ** slot
                    ans = max(ans, (nums[i] & (slot+1)) + dp(i+1, nmask))
            return ans
        return dp(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


impl Solution {
    pub fn maximum_and_sum(nums: Vec<i32>, num_slots: i32) -> i32 {
        let n = nums.len();
        let m = num_slots as usize;
        let max_mask = 3usize.pow(m as u32);
        let mut dp = vec![0; max_mask];
        for mask in 0..max_mask {
            let mut cnt = 0;
            let mut tmp = mask;
            for _ in 0..m {
                cnt += tmp % 3;
                tmp /= 3;
            }
            if cnt >= n { continue; }
            let mut t = mask;
            for i in 0..m {
                if t % 3 < 2 {
                    let nmask = mask + 3usize.pow(i as u32);
                    dp[nmask] = dp[nmask].max(dp[mask] + (nums[cnt] & (i as i32 + 1)));
                }
                t /= 3;
            }
        }
        *dp.iter().max().unwrap()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    maximumANDSum(nums: number[], numSlots: number): number {
        const n = nums.length, m = numSlots;
        const maxMask = Math.pow(3, m);
        const dp = new Array(maxMask).fill(0);
        for (let mask = 0; mask < maxMask; ++mask) {
            let cnt = 0, tmp = mask;
            for (let i = 0; i < m; ++i) {
                cnt += tmp % 3;
                tmp = Math.floor(tmp / 3);
            }
            if (cnt >= n) continue;
            let t = mask;
            for (let i = 0; i < m; ++i) {
                if (t % 3 < 2) {
                    const nmask = mask + Math.pow(3, i);
                    dp[nmask] = Math.max(dp[nmask], dp[mask] + (nums[cnt] & (i+1)));
                }
                t = Math.floor(t / 3);
            }
        }
        return Math.max(...dp);
    }
}

Complexity

⏰ Time complexity: O(3^m * m), where m is numSlots, since each state is processed for each slot.
🧺 Space complexity: O(3^m), for the DP array.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Bitmask Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#