Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Maximum AND Sum of Array

Maximum AND Sum of Array

Master this topic with zero to advance depth.

Maximum AND Sum of Array

Place n integers into numSlots slots (max 2 per slot). The AND sum is the sum of (nums[i] & slotNumber). Return the maximum possible AND sum.

Hard

Examples

Input: nums = [1,2,3,4,5,6], numSlots = 3
Output: 9
Approach 1

Level I: Brute Force (Recursion)

Intuition

Try all possible placements of the nn integers into the numSlotsnumSlots slots. Each slot can take up to 2 integers. This is an exhaustive search of the solution space.

⏱ $O(numSlots^N)$💾 $O(N)$
java
class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        return solve(0, new int[numSlots + 1], nums);
    }
    private int solve(int idx, int[] counts, int[] nums) {
        if (idx == nums.length) return 0;
        int max = 0;
        for (int i = 1; i < counts.length; i++) {
            if (counts[i] < 2) {
                counts[i]++;
                max = Math.max(max, (nums[idx] & i) + solve(idx + 1, counts, nums));
                counts[i]--;
            }
        }
        return max;
    }
}
Approach 2

Level II: Greedy / Simple DP

Intuition

Identify that the problem has overlapping subproblems. Even without a full ternary mask, we can use a simpler memoization based on the current counts array (converted to a string or tuple) to avoid redundant work.

⏱ $O(N \cdot 3^{numSlots})$💾 $O(N \cdot 3^{numSlots})$
java
class Solution {
    Map<String, Integer> memo = new HashMap<>();
    public int maximumANDSum(int[] nums, int numSlots) {
        return solve(0, new int[numSlots + 1], nums);
    }
    private int solve(int idx, int[] counts, int[] nums) {
        if (idx == nums.length) return 0;
        String key = idx + Arrays.toString(counts);
        if (memo.containsKey(key)) return memo.get(key);
        int max = 0;
        for (int i = 1; i < counts.length; i++) {
            if (counts[i] < 2) {
                counts[i]++;
                max = Math.max(max, (nums[idx] & i) + solve(idx + 1, counts, nums));
                counts[i]--;
            }
        }
        memo.put(key, max);
        return max;
    }
}
Approach 3

Level III: Bitmask DP (Ternary / Base-3)

Intuition

Since each slot can hold up to 2 integers, we can represent the state of the slots using a base-3 integer. In this integer, the ii-th digit (in base 3) represents the number of elements in slot i+1i+1 (0, 1, or 2).

Thought Process

  1. Use a recursive function solve(index, mask) where index is the current number in nums we are placing.
  2. The mask is a base-3 representation of slot occupancies.
  3. For each slot j∈[1,numSlots]j \in [1, numSlots]:
    • Check if slot jj has <2< 2 items.
    • If yes, place nums[index] in slot jj, update mask, and take the results.

Pattern: Base-N Bitmasking

⏱ O(N \cdot 3^S) - Where $N$ is `nums.length` and $S$ is `numSlots`.💾 O(3^S) - Memoization table.
java
public class Solution {
    int[] memo;
    int[] pow3;

    public int maximumANDSum(int[] nums, int numSlots) {
        pow3 = new int[numSlots + 1];
        pow3[0] = 1;
        for (int i = 1; i <= numSlots; i++) pow3[i] = pow3[i - 1] * 3;
        memo = new int[pow3[numSlots]];
        return solve(0, 0, nums, numSlots);
    }

    private int solve(int idx, int mask, int[] nums, int numSlots) {
        if (idx == nums.length) return 0;
        if (memo[mask] > 0) return memo[mask] - 1;
        int res = 0;
        for (int i = 0; i < numSlots; i++) {
            int slotVal = (mask / pow3[i]) % 3;
            if (slotVal < 2) {
                res = Math.max(res, (nums[idx] & (i + 1)) + solve(idx + 1, mask + pow3[i], nums, numSlots));
            }
        }
        memo[mask] = res + 1;
        return res;
    }
}
← Previous QuestionCan I Win
Next Question →LRU Cache