Maximum AND Sum of Array
HardPrompt
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 slot1and[4, 6]into slot2is 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.length1 <= numSlots <= 91 <= n <= 2 * numSlots1 <= nums[i] <= 15
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Define a recursive function, let's call it
backtrack(index, slotCounts, currentSum), whereindexis the current number fromnumsto place,slotCountsis an array tracking the occupancy of each slot, andcurrentSumis the accumulated AND sum. - The base case for the recursion is when
indexreaches the end of thenumsarray. At this point, we have a complete placement, so we update a global maximum sum with thecurrentSum. - 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 thecurrentSum, 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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- The state of a subproblem can be defined by
(index, mask), whereindexis the index of the number innumsto be placed, andmaskis an integer representing the occupancy of all slots. - We use a base-3 representation for the
mask: thei-th digit (from right, 0-indexed) in base 3 represents the occupancy (0, 1, or 2) of sloti+1. - Create a 2D memoization table
memo[index][mask]to store the results ofsolve(index, mask). - The recursive function
solve(index, mask)calculates the maximum AND sum for placing numbers fromnums[index]onwards, given the slot occupancies inmask. - 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 callingsolveforindex + 1with an updated mask. - Store the computed maximum sum in the memo table before returning.
Walkthrough
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.
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; }}Complexity
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)`.
Trade-offs
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.
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.
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 themaskby 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
dparray of size3^numSlots, wheredp[mask]stores the maximum AND sum for the placement represented bymask. - Initialize
dp[0] = 0and all otherdpvalues to 0. - Iterate through each
maskfrom0to3^numSlots - 1. - For each
mask, calculate the number of placed items,k. - If
k < n, iterate through allnumSlots. If a slotjis not full in the currentmask:- Calculate the
newMaskthat results from placing an item in slotj. - Update
dp[newMask]with the potentially larger value:dp[newMask] = max(dp[newMask], dp[mask] + (nums[k] & j)).
- Calculate the
- After filling the
dptable, the maximum value in the table is the answer. This is because we might placen < 2 * numSlotsitems, so the final state could be any mask corresponding tonplaced items.
Walkthrough
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.
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.
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`.
Trade-offs
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.
Solutions
Solution
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; }}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 )); } };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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.