2172. Maximum AND Sum of Array LeetCode Solution

Last updated: February 26, 2025

In this guide, you will get 2172. Maximum AND Sum of Array LeetCode Solution with the best time and space complexity. The solution to Maximum AND Sum of Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum AND Sum of Array solution in C++
Maximum AND Sum of Array solution in Java
Maximum AND Sum of Array solution in Python
Additional Resources

2172. Maximum AND Sum of Array LeetCode Solution image

Problem Statement of Maximum AND Sum of Array

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

Complexity Analysis

Time Complexity: O(2^n \cdot n)
Space Complexity: O(2^n)

2172. Maximum AND Sum of Array LeetCode Solution in C++

class Solution {
 public:
  int maximumANDSum(vector<int>& nums, int numSlots) {
    const int n = 2 * numSlots;
    const int nSelected = 1 << n;
    // dp[i] := the maximum value, where i is the bitmask of the selected
    // numbers
    vector<int> dp(nSelected);

    nums.resize(n);

    for (unsigned mask = 1; mask < nSelected; ++mask) {
      const int selected = popcount(mask);
      const int slot = (selected + 1) / 2;  // (1, 2) -> 1, (3, 4) -> 2
      for (int i = 0; i < n; ++i)
        if (mask >> i & 1)  // Assign `nums[i]` to the `slot`-th slot.
          dp[mask] = max(dp[mask], dp[mask ^ 1 << i] + (slot & nums[i]));
    }

    return dp.back();
  }
};
/* code provided by PROGIEZ */

2172. Maximum AND Sum of Array LeetCode Solution in Java

class Solution {
  public int maximumANDSum(int[] nums, int numSlots) {
    final int n = 2 * numSlots;
    final int nSelected = 1 << n;
    // dp[i] := the maximum value, where i is the bitmask of the selected
    // numbers
    int[] dp = new int[nSelected];
    int[] arr = Arrays.copyOf(nums, n);

    for (int mask = 1; mask < nSelected; ++mask) {
      final int selected = Integer.bitCount(mask);
      final int slot = (selected + 1) / 2; // (1, 2) -> 1, (3, 4) -> 2
      for (int i = 0; i < n; ++i)
        if ((mask >> i & 1) == 1) // Assign `arr[i]` to the `slot`-th slot.
          dp[mask] = Math.max(dp[mask], dp[mask ^ 1 << i] + (slot & arr[i]));
    }

    return dp[nSelected - 1];
  }
}
// code provided by PROGIEZ

2172. Maximum AND Sum of Array LeetCode Solution in Python

class Solution:
  def maximumANDSum(self, nums: list[int], numSlots: int) -> int:
    n = 2 * numSlots
    nSelected = 1 << n
    # dp[i] := the maximum value, where i is the bitmask of the selected
    # numbers
    dp = [0] * nSelected

    nums += [0] * (n - len(nums))

    for mask in range(1, nSelected):
      selected = mask.bit_count()
      slot = (selected + 1) // 2  # (1, 2) -> 1, (3, 4) -> 2
      for i, num in enumerate(nums):
        if mask >> i & 1:  # Assign `nums[i]` to the `slot`-th slot.
          dp[mask] = max(dp[mask], dp[mask ^ 1 << i] + (slot & num))

    return dp[-1]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents