Welcome to Subscribe On Youtube

2172. Maximum AND Sum of Array

Description

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• 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)
  
  

• 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)
  }
  

• 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);
  }
  
  

All Problems

All Solutions