Get started

Maximum AND Sum of Array — Hard Problem & Solution

There are numSlots slots numbered 1 through numSlots, and each slot may hold at most two numbers. Every element of nums must be placed in some slot.

Problem statement

There are numSlots slots numbered 1 through numSlots, and each slot may hold at most two numbers. Every element of nums must be placed in some slot.

The AND sum is the sum of number AND slotNumber over every placement. Return the maximum achievable AND sum.

Example 1

Input: nums = [1,2,3,4,5,6], numSlots = 3
Output: 9
Explanation: Placing them as [1,4], [2,6], [3,5] gives 1+0 + 2+2 + 3+1 = 9.

Example 2

Input: nums = [1,3,10,4,7,1], numSlots = 9
Output: 24

Example 3

Input: nums = [8], numSlots = 1
Output: 0
Explanation: 8 AND 1 is 0.

Constraints

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

How to solve Maximum AND Sum of Array

The numbers are interchangeable in the sense that only which slot each lands in matters, so process them in a fixed order and let the state record how full each slot is. A base-3 digit per slot captures that in a single integer.

Approach

  1. Encode the configuration as a base-3 number with one digit per slot, counting 0, 1 or 2 occupants.
  2. The digit sum of a state is how many numbers are already placed, which identifies the next number to place.
  3. From each reachable state, try every slot that is not full, adding nums[placed] & (slot + 1) to the score.
  4. The answer is the best score over states where every number has been placed.

Why it works

Processing the numbers in a fixed order removes the ordering redundancy without losing any assignment, because a placement is fully described by the multiset of slot choices. States only ever grow, so a single forward sweep in increasing state order is a valid topological order.

Complexity

  • Time — O(3^numSlots · numSlots)
  • Space — O(3^numSlots)

Pitfalls

  • A bitmask over 2 * numSlots slot positions also works but doubles the state space for no gain.
  • Slots are numbered from 1, so the AND uses slotIndex + 1.
  • Reading the best answer only from the final full state is wrong when nums is shorter than 2 * numSlots — collect it from every state where all numbers are placed.

Reference solution

Python

from typing import List

def maximumANDSum(nums: List[int], numSlots: int) -> int:
    pow3 = [1]
    for i in range(numSlots):
        pow3.append(pow3[-1] * 3)
    total = pow3[numSlots]
    dp = [0] * total
    best = 0
    for mask in range(total):
        placed = 0
        t = mask
        for _ in range(numSlots):
            placed += t % 3
            t //= 3
        if placed >= len(nums):
            best = max(best, dp[mask])
            continue
        x = nums[placed]
        for s in range(numSlots):
            if (mask // pow3[s]) % 3 >= 2:
                continue
            nxt = mask + pow3[s]
            dp[nxt] = max(dp[nxt], dp[mask] + (x & (s + 1)))
    return best

JavaScript

var maximumANDSum = function(nums, numSlots) {
    var pow3 = [1];
    for (var i = 1; i <= numSlots; i++) pow3.push(pow3[i - 1] * 3);
    var total = pow3[numSlots];
    var dp = [];
    for (var t = 0; t < total; t++) dp.push(0);
    var best = 0;
    for (var mask = 0; mask < total; mask++) {
        var placed = 0, v = mask;
        for (var s = 0; s < numSlots; s++) { placed += v % 3; v = Math.floor(v / 3); }
        if (placed >= nums.length) {
            if (dp[mask] > best) best = dp[mask];
            continue;
        }
        var x = nums[placed];
        for (var j = 0; j < numSlots; j++) {
            if (Math.floor(mask / pow3[j]) % 3 >= 2) continue;
            var next = mask + pow3[j];
            var val = dp[mask] + (x & (j + 1));
            if (val > dp[next]) dp[next] = val;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 195 dynamic programming problems · the whole catalogue