Skip to main content
Talentd

Maximum AND Sum of Array - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationBitmask8 min readAsked at: Google
Practice this problem

Problem Statement

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

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.

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

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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.

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

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(2n * n * S), where S is the number of slots.
Space Complexity: O(2n * S), for the DP table.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

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.

Dynamic Programming with Bit Mask

Time Complexity: O(2n * n * S), where S is the number of slots.
Space Complexity: O(2n * S), for the DP table.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking AssignmentO(numSlots^n)O(numSlots)Good for understanding the placement logic or solving very small inputs
Dynamic Programming with BitmaskO((2·numSlots) · 2^(2·numSlots))O(2^(2·numSlots))Optimal approach for the general case where numSlots ≤ 9

Video Solution

Hardest on Leetcode ?? | One Problem - Four Solutions | Leetcode Weekly Episode 4 | Leetcode 2172 • Vivek Gupta • 3,342 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Maximum AND Sum of Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum XOR Sum of Two Arrays