We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum AND Sum of Array

Number: 2291

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

You are given an integer array nums and an integer numSlots such that 2 * numSlots >= n (where n is the number of elements in nums). There are numSlots slots numbered from 1 to numSlots, and each slot can hold at most two numbers. The AND sum is defined as the sum, over all placements, of the bitwise AND of each number with the slot number it is placed in. The task is to determine the maximum possible AND sum that can be achieved by optimally placing all the numbers into the slots.

Key Insights

  • Use dynamic programming (DP) with state encoding to explore all placements.
  • Since each slot can hold at most two numbers and numSlots is at most 9, we can encode slot occupancy in a compact state (using base-3 representation).
  • The brute-force search space is reduced by memoizing subproblems with DP.
  • At each step, choose a slot that is not completely full, update the state, and add the contribution (nums[i] AND slot index) to the total sum.
  • Bit manipulation is used in computing the AND operation, but the main challenge is the DP state management.

Space and Time Complexity

Time Complexity: O(n * 3^(numSlots)) where n is the length of nums, because for each number, we examine up to numSlots choices over 3^(numSlots) possible states. Space Complexity: O(3^(numSlots)) for the memoization table.

Solution

We solve the problem using a DFS approach with memoization (Top-Down DP). A key idea is maintaining a state that represents the occupancy of each slot. Since each slot can hold 0, 1, or 2 numbers, we encode the state in base-3. For example, if numSlots is 3, then a state might be represented as an integer where each digit (in base 3) corresponds to the count of numbers already placed in that slot.

The algorithm recursively places each number into every possible slot that has room. For each placement, we update the state and accumulate the AND sum (computed as nums[i] AND slot_index). We then use the maximum value among all valid placements. To avoid recomputation, results are cached using memoization where the key is a tuple (index, state).

Data structures:

  • An integer to encode slot occupancy in base 3.
  • A dictionary (or map) for memoization.

The trickiest part is correctly updating and decoding the state. Instead of actually storing an array for each DP state, a single integer is used to represent the state compactly. Each slot’s occupancy is extracted using modular arithmetic and updating is done by adding the appropriate power of 3.

Code Solutions

def maxAndSum(nums, numSlots):
    from functools import lru_cache

    n = len(nums)
    
    # Compute powers of 3 for convenient state encoding.
    pow3 = [3 ** i for i in range(numSlots)]
    
    @lru_cache(maxsize=None)
    def dfs(idx, state):
        # Base case: if all numbers are placed, return 0.
        if idx == n:
            return 0
        max_sum = 0
        # Try every slot to see if we can place nums[idx] into that slot.
        for slot in range(numSlots):
            # Extract current occupancy for this slot.
            count = (state // pow3[slot]) % 3
            if count < 2:  # this slot is not full
                # Update the state: increase the count for this slot.
                new_state = state + pow3[slot]
                # Calculate the AND sum contribution: 
                # note slot numbers are 1-indexed.
                contribution = (nums[idx] & (slot + 1))
                # Recurse to place next number.
                temp = contribution + dfs(idx + 1, new_state)
                max_sum = max(max_sum, temp)
        return max_sum

    return dfs(0, 0)

# Example usage:
nums = [1,2,3,4,5,6]
numSlots = 3
print(maxAndSum(nums, numSlots))  # Output should be 9
← Back to All Questions