HardNo. 2172
Maximum AND Sum of Array — LeetCode 2172 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Array, Dynamic Programming, Bitmask
- Reading time
- 3 min
- Source
- leetcode.com
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.
Example
- 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.
Python solution
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)Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2172. Maximum AND Sum of Array is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0473 | Matchsticks to Square | Medium |
| 0526 | Beautiful Arrangement | Medium |
| 0638 | Shopping Offers | Medium |
| 0698 | Partition to K Equal Sum Subsets | Medium |
| 0805 | Split Array With Same Average | Hard |
| 0943 | Find the Shortest Superstring | Hard |
Frequently asked questions
- How hard is LeetCode 2172. Maximum AND Sum of Array?
LeetCode 2172. Maximum AND Sum of Array is rated Hard on LeetCode.
- What topics does LeetCode 2172. Maximum AND Sum of Array cover?
LeetCode 2172. Maximum AND Sum of Array is tagged Bit Manipulation, Array, Dynamic Programming and Bitmask on LeetCode.