# Maximum AND Sum of Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-and-sum-of-array)
Canonical: https://scaleengineer.com/dsa/problems/maximum-and-sum-of-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** 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 possible **AND sum** of_ `nums` _given_ `numSlots` _slots._

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

**Example 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.

**Constraints:**

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

# Approaches
## Brute Force Backtracking
The most straightforward approach is to try every possible valid placement of numbers into slots. We can use a backtracking algorithm to explore all combinations. We process the numbers from the `nums` array one by one. For each number, we try to place it in every slot that is not yet full (i.e., contains fewer than two numbers). We recursively build a solution and keep track of the maximum AND sum found across all valid placements.
**Time:** O(numSlots^n)

For each of the `n` numbers, we have up to `numSlots` choices for placement. This leads to a decision tree of depth `n` with a branching factor of up to `numSlots`, resulting in a time complexity that is roughly exponential in `n`. · **Space:** O(n)

The space complexity is determined by the depth of the recursion stack, which is equal to the number of elements `n` in the `nums` array.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on any reasonably sized input.
### Explanation
This method uses a recursive function to explore the decision tree of placements. The state of our recursion is determined by which number we are currently placing (`index`) and the current occupancy of each slot (`slotCounts`).

For `nums[0]`, we can place it in any of the `numSlots`. Let's say we place it in slot `j`. Then for `nums[1]`, we again try to place it in any slot that is not full. We continue this process until all numbers are placed. The AND sum for a complete placement is calculated, and we find the maximum among all such placements.

```java
class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        // slotCounts[i] stores the number of elements in slot i+1
        int[] slotCounts = new int[numSlots];
        return backtrack(nums, 0, slotCounts);
    }

    private int backtrack(int[] nums, int index, int[] slotCounts) {
        if (index == nums.length) {
            return 0;
        }

        int maxSum = 0;
        // Try placing nums[index] in each slot
        for (int i = 0; i < slotCounts.length; i++) {
            if (slotCounts[i] < 2) {
                slotCounts[i]++;
                int currentSum = (nums[index] & (i + 1)) + backtrack(nums, index + 1, slotCounts);
                maxSum = Math.max(maxSum, currentSum);
                slotCounts[i]--; // backtrack
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- Define a recursive function, let's call it `backtrack(index, slotCounts, currentSum)`, where `index` is the current number from `nums` to place, `slotCounts` is an array tracking the occupancy of each slot, and `currentSum` is the accumulated AND sum.
- The base case for the recursion is when `index` reaches the end of the `nums` array. At this point, we have a complete placement, so we update a global maximum sum with the `currentSum`.
- In the recursive step, iterate through all available slots from 1 to `numSlots`.
- For each slot, if it's not full (i.e., has fewer than 2 numbers), place `nums[index]` into it.
- To do this, increment the count for that slot, add `(nums[index] & slotNumber)` to the `currentSum`, and make a recursive call for the next number: `backtrack(index + 1, ...)`.
- After the recursive call returns, backtrack by undoing the choice: decrement the slot's count.

## Dynamic Programming with Memoization
The brute-force backtracking approach is slow because it repeatedly solves the same subproblems. We can significantly improve performance by using memoization, a top-down dynamic programming technique. We store the results of subproblems in a cache (or memo table) so that we don't have to recompute them. A subproblem is uniquely identified by the current index of the number to be placed and the current state of all slots.
**Time:** O(n * numSlots * 3^numSlots)

There are `n * 3^numSlots` possible states `(index, mask)`. For each state, we iterate through `numSlots` to make a decision. Thus, the total time complexity is the product of these three factors. · **Space:** O(n * 3^numSlots)

The space is dominated by the memoization table, which has `n` rows and `3^numSlots` columns. The recursion stack depth adds `O(n)`.
**Pros:** Significantly faster than brute force and efficient enough to pass within the given constraints.; Guarantees finding the optimal solution.
**Cons:** The space complexity is quite high, proportional to `n * 3^numSlots`.
### Explanation
The state of our DP can be `(index, mask)`. `index` refers to `nums[index]`, the number we are about to place. `mask` is a compact representation of the occupancy of the `numSlots`. Since each slot can hold 0, 1, or 2 items, we can use a number in base 3 to represent the occupancies. For `numSlots`, the mask will be an integer from `0` to `3^numSlots - 1`.

For example, with `numSlots = 3`, if slot 1 has 1 item, slot 2 has 2, and slot 3 has 0, the mask can be `1*3^0 + 2*3^1 + 0*3^2 = 7`.

The function `solve(index, mask)` will return the maximum possible AND sum from placing `nums[index], nums[index+1], ...` given the slot configuration represented by `mask`.

```java
class Solution {
    Integer[][] memo;
    int[] p3;

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

    private int solve(int[] nums, int numSlots, int index, int mask) {
        if (index == nums.length) {
            return 0;
        }
        if (memo[index][mask] != null) {
            return memo[index][mask];
        }

        int maxSum = 0;
        for (int slot = 1; slot <= numSlots; slot++) {
            int occupancy = (mask / p3[slot - 1]) % 3;
            if (occupancy < 2) {
                int currentSum = (nums[index] & slot) + solve(nums, numSlots, index + 1, mask + p3[slot - 1]);
                maxSum = Math.max(maxSum, currentSum);
            }
        }

        return memo[index][mask] = maxSum;
    }
}
```
### Algorithm
- The state of a subproblem can be defined by `(index, mask)`, where `index` is the index of the number in `nums` to be placed, and `mask` is an integer representing the occupancy of all slots.
- We use a base-3 representation for the `mask`: the `i`-th digit (from right, 0-indexed) in base 3 represents the occupancy (0, 1, or 2) of slot `i+1`.
- Create a 2D memoization table `memo[index][mask]` to store the results of `solve(index, mask)`.
- The recursive function `solve(index, mask)` calculates the maximum AND sum for placing numbers from `nums[index]` onwards, given the slot occupancies in `mask`.
- Before computing, check the memo table. If a result exists, return it.
- In the function, iterate through each slot. If a slot is not full, calculate the potential sum by placing `nums[index]` in it and recursively calling `solve` for `index + 1` with an updated mask.
- Store the computed maximum sum in the memo table before returning.

## Optimized Dynamic Programming on Slot Occupancy
This approach further optimizes the dynamic programming solution. We observe that the `index` of the number we need to place is not an independent state variable. It's determined by the number of items already placed, which can be calculated from the occupancy `mask`. By removing `index` from the DP state, we can reduce both time and space complexity.
**Time:** O(numSlots * 3^numSlots)

We iterate through `3^numSlots` masks. For each mask, we calculate `k` (which takes `O(numSlots)`) and then iterate through `numSlots` again. The calculation of `k` can be optimized, but the inner loop dominates, leading to this complexity. · **Space:** O(3^numSlots)

The space is dominated by the DP table, which has a size of `3^numSlots`.
**Pros:** Most efficient solution for the given constraints.; Reduces both time and space complexity compared to the non-optimized DP approach.
**Cons:** The logic, especially for the state transitions and deriving the item index `k`, can be more complex to grasp than the previous DP approach.
### Explanation
The core idea is that if a `mask` represents a state where `k` items have been placed, the next item to be placed must be `nums[k]`. The number of placed items `k` is simply the sum of the occupancies of all slots, which can be found by summing the digits of the `mask` in its base-3 representation.

This leads to a DP state `dp[mask]` which stores the maximum AND sum for a placement corresponding to `mask`. We can build this solution iteratively.

```java
class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        int n = nums.length;
        int[] p3 = new int[numSlots + 1];
        p3[0] = 1;
        for (int i = 1; i <= numSlots; i++) {
            p3[i] = p3[i - 1] * 3;
        }
        int maskSize = p3[numSlots];
        int[] dp = new int[maskSize];

        for (int mask = 0; mask < maskSize; mask++) {
            int k = 0; // Number of elements placed
            int tempMask = mask;
            for (int i = 0; i < numSlots; i++) {
                k += tempMask % 3;
                tempMask /= 3;
            }

            if (k >= n) {
                continue;
            }

            for (int slot = 1; slot <= numSlots; slot++) {
                int occupancy = (mask / p3[slot - 1]) % 3;
                if (occupancy < 2) {
                    int newMask = mask + p3[slot - 1];
                    int currentVal = dp[mask] + (nums[k] & slot);
                    dp[newMask] = Math.max(dp[newMask], currentVal);
                }
            }
        }
        
        int maxAndSum = 0;
        for (int val : dp) {
            maxAndSum = Math.max(maxAndSum, val);
        }

        return maxAndSum;
    }
}
```
This iterative implementation is a "push" style DP, where we compute the values for future states based on the current state.
### Algorithm
- The DP state can be optimized to depend only on the `mask`. The index of the number to place, `k`, can be derived from the `mask` by summing its base-3 digits, which gives the total number of items already placed.
- We can use a bottom-up (iterative) DP approach. Create a `dp` array of size `3^numSlots`, where `dp[mask]` stores the maximum AND sum for the placement represented by `mask`.
- Initialize `dp[0] = 0` and all other `dp` values to 0.
- Iterate through each `mask` from `0` to `3^numSlots - 1`.
- For each `mask`, calculate the number of placed items, `k`.
- If `k < n`, iterate through all `numSlots`. If a slot `j` is not full in the current `mask`:
  - Calculate the `newMask` that results from placing an item in slot `j`.
  - Update `dp[newMask]` with the potentially larger value: `dp[newMask] = max(dp[newMask], dp[mask] + (nums[k] & j))`.
- After filling the `dp` table, the maximum value in the table is the answer. This is because we might place `n < 2 * numSlots` items, so the final state could be any mask corresponding to `n` placed items.

# Solutions
### Java

```java
class Solution {
public
  int maximumANDSum(int[] nums, int numSlots) {
    int n = nums.length;
    int m = numSlots << 1;
    int[] f = new int[1 << m];
    int ans = 0;
    for (int i = 0; i < 1 << m; ++i) {
      int cnt = Integer.bitCount(i);
      if (cnt > n) {
        continue;
      }
      for (int j = 0; j < m; ++j) {
        if ((i >> j & 1) == 1) {
          f[i] =
              Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j / 2 + 1)));
        }
      }
      ans = Math.max(ans, f[i]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int maximumANDSum ( vector < int >& nums , int numSlots ) { int n = nums . size (); int m = numSlots << 1 ; int f [ 1 << m ]; memset ( f , 0 , sizeof ( f )); for ( int i = 0 ; i < 1 << m ; ++ i ) { int cnt = __builtin_popcount ( i ); if ( cnt > n ) { continue ; } for ( int j = 0 ; j < m ; ++ j ) { if ( i >> j & 1 ) { f [ i ] = max ( f [ i ], f [ i ^ ( 1 << j )] + ( nums [ cnt - 1 ] & ( j / 2 + 1 ))); } } } return * max_element ( f , f + ( 1 << m )); } };
```

### Python

```python
class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int: n = len(nums) m = numSlots << 1 f = [0] * (1 << m) for i in range(1 << m): cnt = i . bit_count() if cnt > n: continue for j in range(m): if i >> j & 1: f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j // 2 + 1))) return max(f)

```