Maximum AND Sum of Array

Maximum AND Sum of Array

What is this problem about?

The Maximum AND Sum of Array problem gives you an integer array nums and an integer numSlots. There are numSlots slots, numbered from 1 to numSlots. You must place every element of the array into one of these slots. A single slot can hold at most two numbers. The score of placing a number in a slot is number AND slot_number (bitwise AND). Your goal is to return the maximum possible total score after placing all numbers.

Why is this asked in interviews?

This is an elite Hard-level DP problem. Interviewers from Google and Amazon ask it to assess a candidate's mastery of Bitmasking DP combined with Base-3 (Ternary) logic. Because each slot can hold up to 2 items, a standard binary bitmask (0 or 1) isn't enough. Candidates must prove they can model states dynamically using higher-base representations to avoid combinatorial explosion.

Algorithmic pattern used

This problem strictly relies on Dynamic Programming with Base-3 State Masking. We need to track the "capacity" of each slot. Since a slot can hold 0, 1, or 2 items, we can represent the state of all numSlots (max 9 slots) as a single integer in Base-3. A Base-3 number with 9 digits tops out at $3^9 = 19683$, which is a very small, highly cacheable state space! We run a recursive DFS that takes the (current_num_index, base3_mask). Inside, we iterate through all slots from 1 to numSlots. If the slot's Base-3 digit in the mask is $< 2$, we place the number there, add (num AND slot), update the mask, and recurse. Memoization caches the max score for each mask.

Example explanation

nums = [1, 2, 3], numSlots = 2. Mask starts at 00 (Base 3: Slot 2 has 0, Slot 1 has 0). Processing nums[0] = 1:

• Place in Slot 1: Score is 1 AND 1 = 1. Mask becomes 01. Recurse.
  • Processing nums[1] = 2:
    • Place in Slot 1 (Mask 01 -> < 2, valid). Score 2 AND 1 = 0. Mask 02. Recurse.
    • Place in Slot 2 (Mask 01 -> < 2, valid). Score 2 AND 2 = 2. Mask 11. Recurse. By evaluating all branches using DFS and caching the results based on the Base-3 integer representation of the slots, the algorithm quickly converges on the optimal distribution layout.

Common mistakes candidates make

The most frequent mistake is trying to use a standard binary bitmask. Candidates will artificially duplicate the slots (e.g., Slot 1A, Slot 1B) to use a binary mask. While this works conceptually, it massively inflates the state space and often leads to Time Limit Exceeded errors due to redundant calculations. Understanding how to extract and update digits in Base-3 using / and % math is crucial for the optimal solution.

Interview preparation tip

When dealing with state DP where items can have a limited count $> 1$, always use an integer mask representing a higher base. To get the $i$-th digit of a mask in base $B$: (mask / (B^i)) % B. To add 1 to the $i$-th digit of a mask in base $B$: mask + (B^i). Memorizing these two math operations allows you to implement Base-3, Base-4, or Base-K masks effortlessly.