Maximum AND Sum of Array solution and explanation
Google
5 more videos on this problem
Hardest on Leetcode ?? | One Problem - Four Solutions | Leetcode Weekly Episode 4 | Leetcode 2172Vivek Gupta · 24:47 · 3K views
2172. Maximum AND Sum of Array || LeetCode 2172 || LeetCode Weekly Contest 280Bro Coders · 22:39 · 3K views
2172. Maximum AND Sum of Array (Leetcode Hard)Programming Live with Larry · 21:57 · 1K views
【每日一题】LeetCode 2172. Maximum AND Sum of ArrayHuifeng Guan · 40:05 · 1K views
2172 Maximum AND Sum of Array | LeetCode 2172 | LeetCode Weekly Contest 280Vidit Shukla · 14:49 · 489 views
LeetCode 2172: Maximum AND Sum of ArrayAlitaCode · 30:26 · 3 views
The 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 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
Approach overview
Problem Overview: You are given an array nums and numSlots slots where each slot can hold at most two numbers. Placing a number x in slot i contributes x & i to the score. The goal is to assign every number to a slot so the total AND sum is maximized.
Approach 1: Backtracking Assignment (Exponential Time)
This method tries every possible assignment of numbers to slots. Maintain a counter for how many numbers each slot currently holds (maximum two). Recursively place the next number into any slot with available capacity and accumulate the contribution nums[i] & slotIndex. The algorithm explores the full search tree of placements and tracks the best score found.
The time complexity is roughly O((numSlots^n)) in the worst case because each number may be placed in multiple slots. Space complexity is O(numSlots) for recursion state. This approach is useful for understanding the problem structure and verifying small inputs, but it becomes slow as the search space grows.
Approach 2: Dynamic Programming with Bitmask (Optimal)
The key observation is that each slot can hold exactly two positions. Instead of tracking slots directly, treat the problem as assigning numbers to 2 × numSlots positions. Use a bitmask where each bit represents whether a position is already filled. If the mask has k bits set, you are assigning the k-th number in nums.
For every unused position in the mask, compute the slot index as (position / 2) + 1 and add nums[k] & slot. Update the DP state for the new mask. This converts the exponential assignment problem into a manageable state transition over bitmasks.
The time complexity becomes O((2 × numSlots) × 2^(2 × numSlots)) because each mask tries filling the remaining positions. Space complexity is O(2^(2 × numSlots)) for the DP table. Since numSlots ≤ 9, the state space is small enough to compute efficiently.
This approach heavily relies on bitmask state compression and dynamic programming transitions over subsets. The input structure itself comes from a simple array, but the optimization comes from representing assignments compactly with bits.
Recommended for interviews: Start by explaining the brute-force backtracking approach to show you understand the assignment constraints. Then transition to the bitmask DP optimization. Interviewers typically expect the DP with bitmask solution because it reduces the exponential branching into a structured state space and demonstrates strong subset-DP skills.
Approach 1: Backtracking Approach
This approach explores all possible placements of the numbers into the slots and calculates the AND sum for each configuration. It keeps track of the maximum AND sum encountered. The constraints allow this brute-force-like method to be feasible given that n is small.
def max_and_sum(nums, numSlots):
def backtrack(index, slots):
if index == len(nums):
return 0
max_sum = 0
for i in range(numSlots):
for j in range(2): # Each slot can have max 2 numbers
if slots[i][j] == -1: # Check slot availability
slots[i][j] = nums[index]
current_and_sum = (nums[index] & (i + 1)) + backtrack(index + 1, slots)
max_sum = max(max_sum, current_and_sum)
slots[i][j] = -1 # Backtrack
break
return max_sum
slots = [[-1, -1] for _ in range(numSlots)]
return backtrack(0, slots)
# Example usage:
# print(max_and_sum([1, 2, 3, 4, 5, 6], 3)) # Output: 9#include <vector>
#include <algorithm>
int backtrack(std::vector<int>& nums, int index, std::vector<std::vector<int>>& slots) {
if (index == nums.size()) return 0;
int max_sum = 0;
for (int i = 0; i < slots.size(); ++i) {
for (int j = 0; j < 2; ++j) {
if (slots[i][j] == -1) {
slots[i][j] = nums[index];
int current_and_sum = (nums[index] & (i + 1)) + backtrack(nums, index + 1, slots);
max_sum = std::max(max_sum, current_and_sum);
slots[i][j] = -1;
break;
}
}
}
return max_sum;
}
int maxAndSum(std::vector<int>& nums, int numSlots) {
std::vector<std::vector<int>> slots(numSlots, std::vector<int>(2, -1));
return backtrack(nums, 0, slots);
}
// Example usage:
// int result = maxAndSum(std::vector<int>{1, 2, 3, 4, 5, 6}, 3);
// std::cout << result << std::endl; // Output: 9The function max_and_sum uses a backtracking approach to find the maximum AND sum. The helper function backtrack attempts to place each number from nums into available slots recursively, keeping track of the maximum AND combination.
Time Complexity: O(Sn), where S is the number of slots. In the worst case, we explore all permutations.
Space Complexity: O(n), due to the recursion stack.
Approach 2: Dynamic Programming with Bit Mask
This approach employs dynamic programming and bit masking to efficiently calculate the maximum AND sum. Each state in the DP table represents a combination of slots filled and their respective configurations.
public class Solution {
public int maxAndSum(int[] nums, int numSlots) {
int n = nums.length;
int[][] dp = new int[1 << n][numSlots + 1];
for (int mask = 0; mask < (1 << n); mask++) {
int count = Integer.bitCount(mask);
if (count % 2 == 1) continue;
for (int slot = 1; slot <= numSlots; slot++) {
int prev = ((1 << count / 2) - 1) << (n - count);
for (int i = prev; (i & mask) == 0; i = (i - prev - 1) & prev) {
int subsetSum = slot * (nums[count / 2] & slot);
dp[prev | mask][slot] = Math.max(dp[prev | mask][slot], dp[mask][slot - 1] + subsetSum);
}
}
}
return dp[(1 << n) - 1][numSlots];
}
public static void main(String[] args) {
Solution solution = new Solution();
int result = solution.maxAndSum(new int[]{1, 2, 3, 4, 5, 6}, 3);
System.out.println(result); // Output: 9
}
}function maxAndSum(nums, numSlots) {
const n = nums.length;
const dp = Array(1 << n).fill().map(() => Array(numSlots + 1).fill(0));
for (let mask = 0; mask < (1 << n); mask++) {
const count = countBits(mask);
if (count % 2 === 1) continue;
for (let slot = 1; slot <= numSlots; slot++) {
const prev = ((1 << (count / 2)) - 1) << (n - count);
for (let i = prev; (i & mask) === 0; i = (i - prev - 1) & prev) {
const subsetSum = slot * (nums[count / 2 | 0] & slot);
dp[prev | mask][slot] = Math.max(dp[prev | mask][slot], dp[mask][slot - 1] + subsetSum);
}
}
}
return dp[(1 << n) - 1][numSlots];
}
function countBits(x) {
let count = 0;
while (x > 0) {
count += x & 1;
x >>= 1;
}
return count;
}
// Example usage:
// console.log(maxAndSum([1, 2, 3, 4, 5, 6], 3)); // Output: 9This Java solution utilizes a dynamic programming table where each state is denoted by a bit mask representing numbers used and slots filled. It optimally calculates the maximum AND sum using bottom-up DP.
Time Complexity: O(2n * n * S), where S is the number of slots.
Space Complexity: O(2n * S), for the DP table.
Approach 3: Default Approach
function maximumANDSum(nums: number[], numSlots: number): number {
const n = nums.length;
const m = numSlots << 1;
const f: number[] = new Array(1 << m).fill(0);
for (let i = 0; i < 1 << m; ++i) {
const cnt = i
.toString(2)
.split('')
.filter(c => c === '1').length;
if (cnt > n) {
continue;
}
for (let j = 0; j < m; ++j) {
if (((i >> j) & 1) === 1) {
f[i] = Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & ((j >> 1) + 1)));
}
}
}
return Math.max(...f);
}func maximumANDSum(nums []int, numSlots int) int {
n := len(nums)
m := numSlots << 1
f := make([]int, 1<<m)
for i := range f {
cnt := bits.OnesCount(uint(i))
if cnt > n {
continue
}
for j := 0; j < m; j++ {
if i>>j&1 == 1 {
f[i] = max(f[i], f[i^(1<<j)]+(nums[cnt-1]&(j/2+1)))
}
}
}
return slices.Max(f)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(Sn), where S is the number of slots. In the worst case, we explore all permutations. |
| Dynamic Programming with Bit Mask | Time Complexity: O(2n * n * S), where S is the number of slots. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Assignment | O(numSlots^n) | O(numSlots) | Good for understanding the placement logic or solving very small inputs |
| Dynamic Programming with Bitmask | O((2·numSlots) · 2^(2·numSlots)) | O(2^(2·numSlots)) | Optimal approach for the general case where numSlots ≤ 9 |
Frequently asked questions
Is Maximum AND Sum of Array easy or hard?
Maximum AND Sum of Array is classified as a Hard problem because it requires recognizing a state compression strategy using bitmask dynamic programming and correctly mapping numbers to slot positions.
Maximum AND Sum of Array Python/Java solution
Python solutions typically use recursion with memoization or iterative DP with bitmasks. Java implementations often use an integer DP array indexed by mask and compute the slot index using popcount operations.
How to solve Maximum AND Sum of Array in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of assignments between numbers and slots. The practical optimal method uses dynamic programming with bitmask states, which runs in O((2·numSlots) · 2^(2·numSlots)).
What is the best approach for Maximum AND Sum of Array?
Dynamic Programming with a bitmask is the most efficient approach. Each bit in the mask represents whether a slot position is filled, and the number of set bits determines which element from nums is being assigned. This reduces the assignment search space to about O((2·numSlots) · 2^(2·numSlots)).
Is Maximum AND Sum of Array asked at Google/Amazon/Meta?
Problems involving bitmask dynamic programming and assignment optimization are common in interviews at companies like Google, Amazon, and Meta. This specific problem tests subset DP and state compression techniques that frequently appear in hard interview questions.
What data structure is used in Maximum AND Sum of Array?
The main technique uses a bitmask to represent slot occupancy and a dynamic programming array to store the best score for each state. Arrays and bit manipulation operations like popcount and bit checks are heavily used.
What is the time complexity of Maximum AND Sum of Array?
The optimal DP with bitmask solution runs in O((2 × numSlots) × 2^(2 × numSlots)) time with O(2^(2 × numSlots)) space. A brute-force backtracking approach can be much slower because it explores many possible slot assignments for each number.