2172. Maximum AND Sum of Array

HardBit ManipulationArrayDynamic ProgrammingBitmask
Leetcode Link

Problem Description

The given problem involves an array of integers nums and an integer numSlots. The size of the array nums is denoted by n, and the condition is that twice the number of numSlots should be greater than or equal to n. This implies we have numSlots where each slot can hold at most two numbers from nums.

The objective is to place all the integers in nums into the numSlots in a way that maximizes the "AND sum". The AND sum is calculated by performing a bitwise AND operation between each number and the number of the slot it is placed in and then summing these values together. Since each slot can hold two numbers, the maximum AND sum will depend on how the numbers are distributed across the slots.

The problem asks us to return the maximum possible AND sum given the numbers in nums and the available numSlots.

Intuition

The solution involves using dynamic programming to calculate the maximum AND sum. Our dynamic programming state is defined by f, which is an array representing all possible placements of the numbers in nums into the numSlots. More specifically, the index i in f[i] represents a bitmask, where each bit indicates whether a slot has been filled or not (and if so, by how many numbers). The size of the array f is 1 << m, where m is twice the number of numSlots, because each slot may be filled with 0, 1, or 2 numbers.

Here's the approach to arriving at the solution:

  1. Initialize the f array with zeros, which will store the maximum AND sum for each state (each possible way to fill the slots).

  2. Iterate over all possible states i of the f array, which are represented as bitmasks. We use the number of bits set in i to determine how many numbers have been placed already (cnt).

  3. Skip the iterations where cnt exceeds n, as this would represent an invalid placement where more numbers are placed than available.

  4. For each state i and for each possible slot j, if that slot (j) is occupied in this state (i >> j & 1 is true), then we calculate a new AND sum by:

    • Removing the number from slot j (i ^ (1 << j)) to find the previous state.
    • Adding the AND operation of the removed number (nums[cnt - 1]) and its respective slot number (j // 2 + 1).

  5. For each state, we maximize f[i] with the newly calculated AND sum if it's greater than the current f[i].

  6. Continue this process until all states have been evaluated.

  7. The maximum AND sum will be the maximum value in the f array after evaluating all states.

The intuition behind this approach is that we explore each possible way to place numbers into slots, track what the AND sum would be for each configuration, and use dynamic programming to efficiently compute the maximum possible AND sum we could get from such placements.

Learn more about Dynamic Programming and Bitmask patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The implementation of the solution uses a dynamic programming approach to solve the problem. Here's how it works step by step referring to the solution provided:

  1. Initialization: Create an array 'f' that will store the maximum AND sum for every bitmask state. As there are numSlots which can each contain up to two numbers, the array size is 1 << (2 * numSlots). The bitmask has 2 * numSlots bits because each slot can be in one of three states - empty, with one number, or with two numbers.

    1f = [0] * (1 << m)

  2. Iterating Over States: Iterate over all possible states of placing n numbers in numSlots. Each state is represented as a bitmask i of size m.

    1for i in range(1 << m):

  3. Bit Counting: Calculate how many bits (numbers) have been placed already using the bit_count() method on the bitmask. If this count cnt exceeds the length of nums, the current bitmask should not be considered as it represents placing more numbers than are available.

    1cnt = i.bit_count()
2if cnt > n:
3    continue

  4. Traversing The Bits in the Bitmask: For every possible slot j (0 to m-1), check if it is used in state 'i' and calculate a new sum considering the number placed in that slot.

    1for j in range(m):
2    if i >> j & 1:

  5. Calculating the AND Sum: Use the previous state i ^ (1 << j) to look up the previous maximum AND sum and add the AND operation between the last-placed number nums[cnt - 1] and the slot index j // 2 + 1. The slot index is j // 2 + 1 because 'j' represents each possible space in the slots, and the same slot number can appear twice.

    1f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j // 2 + 1)))

  6. Maximization Step: The dynamic programming essence is here, where we continuously maximize the entry f[i] with the newly computed AND sum if it’s greater. This will ensure that f[i] stores the maximum AND sum we can achieve for state 'i'.

  7. Getting the Result: The final answer is the maximum value in the f array, which represents the maximum AND sum over all bitmasks representing different ways to fill the slots.

    1return max(f)

The algorithm's time complexity is mainly determined by the two nested loops. The outer loop runs 1 << m times, where m = 2 * numSlots, and the inner loop runs 'm' times, making it O(m * 2^m) in the worst case. Although this seems exponential, the constraint 2 * numSlots >= n allows it to work because the problem size is limited.

The approach capitalizes on dynamic programming to store the intermediate results associated with each possible placement state. Through optimal substructure and overlapping subproblems, it ensures that the final array entry f contains the maximum possible AND sum given numSlots slots.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

To illustrate the solution approach, let's take a small example:

Suppose nums = [1, 2, 3] and numSlots = 2. Since we have 3 numbers, we need numSlots such that 2 * numSlots >= 3 -- which holds true in our case (2 slots * 2 numbers per slot = 4 positions available).

  1. The bitmask m will be twice the number of slots, so m = 2 * numSlots = 4. The possible states will be [0000, 0001, 0010, 0011, ... , 1111], representing the empty slots and how they get filled respectively.

  2. Initialize f = [0] * (1 << m) to store the maximum AND sums.

  3. Start iterating over all possible states of the bitmask from [0000 to 1111].

  4. For each state i, calculate how many 1s are in its binary representation to know how many numbers have been placed. For example, the state 0011 means 2 numbers have been placed already.

  5. If cnt (count of numbers placed) exceeds the number of available numbers (n), this state is skipped because it's not valid.

  6. If not skipped, for each slot j from 0 to m - 1, check if number j is already placed. If yes, we look at the state i ^ (1 << j) (the state before placing number j) to see the maximum AND sum from there.

  7. Add to this sum the AND operation (bitwise) of the last number taken and its respective slot number. For instance:

    • If cnt = 2, it means that nums[cnt - 1] = nums[1] = 2.
    • If we are checking slot j = 1, which corresponds to slot number 1 // 2 + 1 = 1. Therefore, we perform 2 & 1.

  8. Set f[i] to the maximum of its previous value and the new calculated AND sum.

  9. After finishing the iteration for all states, max(f) will give us the maximum AND sum.

Here, let's calculate it step by step:

  • For 0010, cnt = 1. We place nums[0] = 1 in slot 1 (j = 1 means slot number 0). The AND sum is 1 & 1 = 1. So f[0010] = 1.
  • For 0100, cnt = 1. We place nums[0] = 1 in slot 2 (j = 2 means slot number 1). The AND sum is 1 & 1 = 1. So f[0100] = 1.
  • For 0110, cnt = 2. We place nums[1] = 2 in slot 1, with f[0100] being the previous state. The AND sum 2 & 1 = 0, but f[0100] = 1 from previous placement. So f[0110] = max(f[0110], f[0100] + 0) = 1.

Repeat for each state to fill in f. The final maximum AND sum can be found as max(f).

In this example, the maximum AND sum will be achieved by placing numbers in such a way that maximizes each bitwise AND with respective slot numbers. After running the full dynamic programming process, we'll get the maximum possible AND sum which would be returned as the answer.

Solution Implementation

1class Solution:
2    def maximumANDSum(self, nums: List[int], num_slots: int) -> int:
3        num_elements = len(nums)  # Number of elements in the list
4        slot_states = num_slots << 1  # Total number of slots * 2 (for tracking two elements per slot)
5        dp = [0] * (1 << slot_states)  # Dynamic programming table sized for all possible slot combinations
6      
7        # Iterating over all possible combinations of slots
8        for state in range(1 << slot_states):
9            cnt = bin(state).count('1')  # Count how many slots are already occupied in this state
10            if cnt > num_elements:
11                continue  # Skip states with more occupied slots than available elements
12          
13            # For each slot in the current state
14            for slot_bit_index in range(slot_states):
15                # Check if the slot is occupied in the current state
16                if state & (1 << slot_bit_index):
17                    # Calculate new state after freeing the slot
18                    new_state = state ^ (1 << slot_bit_index)
19                    # Calculate the corresponding AND sum
20                    # Note: (slot_bit_index // 2 + 1) to get the slot number (1-indexed)
21                    and_sum = (nums[cnt - 1] & (slot_bit_index // 2 + 1))
22                    # Update the dp table if a better AND sum is found
23                    dp[state] = max(dp[state], dp[new_state] + and_sum)
24        # Returning the maximum AND sum from the last state, which includes all elements in num
25        return max(dp)
26
1class Solution {
2
3    // Method to find the maximum AND sum with nums array and given number of slots 
4    public int maximumANDSum(int[] nums, int numSlots) {
5        int numElements = nums.length; // Number of elements in the nums array
6        int maxStates = numSlots << 1; // Each slot can hold at most two numbers (states represented with bit manipulation)
7        int[] dp = new int[1 << maxStates]; // Dynamic programming table to store maximum AND sum for each possible state
8        int maxAndSum = 0; // Variable to store the final maximum AND sum
9
10        // Iterate through all possible states (combinations of filled slots)
11        for (int state = 0; state < (1 << maxStates); ++state) {
12            int count = Integer.bitCount(state); // Count the number of slots filled in the current state
13            // Skip if the count exceeds the number of elements that can be placed
14            if (count > numElements) {
15                continue;
16            }
17          
18            // Iterate through all possible slots to place the current element
19            for (int slot = 0; slot < maxStates; ++slot) {
20                // Check if the current slot is occupied in the state
21                if ((state >> slot & 1) == 1) {
22                    // Calculate the new state by removing the current element from the slot
23                    int previousState = state ^ (1 << slot);
24                    // Calculate the AND sum for the current state by adding the AND of the element with half the slot index plus one
25                    dp[state] = Math.max(dp[state], dp[previousState] + (nums[count - 1] & ((slot >> 1) + 1)));
26                }
27            }
28            // Update the maximum AND sum found so far
29            maxAndSum = Math.max(maxAndSum, dp[state]);
30        }
31        // Return the maximum AND sum
32        return maxAndSum;
33    }
34}
35
1#include <vector>
2#include <cstring>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8    // Function to calculate the maximum AND sum for 'nums' with 'numSlots'
9    int maximumANDSum(vector<int>& nums, int numSlots) {
10        int numElements = nums.size();
11      
12        // Each slot can hold two items, so we shift left to get total positions
13        int totalPositions = numSlots << 1;
14      
15        // State array to store the maximum AND sum for each combination
16        int dp[1 << totalPositions];
17      
18        // Initialize the state array
19        memset(dp, 0, sizeof(dp));
20      
21        // Iterate through all possible combinations of slots
22        for (int i = 0; i < (1 << totalPositions); ++i) {
23            // Count the number of set bits (occupied positions)
24            int countSetBits = __builtin_popcount(i);
25          
26            // If the count exceeds the number of elements, continue to the next iteration
27            if (countSetBits > numElements) {
28                continue;
29            }
30          
31            // Iterate through all possible positions
32            for (int pos = 0; pos < totalPositions; ++pos) {
33                // Check if the position is occupied
34                if (i >> pos & 1) {
35                    // Update the dp state with the maximum value between the current state and
36                    // the state with the position 'pos' removed, plus the AND sum for the current number
37                    // and the current slot (which is given by `position / 2 + 1`)
38                    dp[i] = max(dp[i], dp[i ^ (1 << pos)] + (nums[countSetBits - 1] & (pos / 2 + 1)));
39                }
40            }
41        }
42      
43        // Find and return the maximum AND sum from the state array
44        return *max_element(dp, dp + (1 << totalPositions));
45    }
46};
47
1function maximumANDSum(nums: number[], numSlots: number): number {
2    const numCount = nums.length; // Total number of elements in 'nums' array
3    const slotMasks = numSlots << 1; // Total number of slot masks, as each slot can take up 2 values
4    const dp: number[] = new Array(1 << slotMasks).fill(0); // Dynamic programming (dp) array to store intermediate results
5
6    // Iterate over all possible combinations of slot allocations
7    for (let mask = 0; mask < 1 << slotMasks; ++mask) {
8        // Count the number of occupied slots in this combination
9        const occupiedSlotsCount = mask.toString(2).split('').filter(bit => bit === '1').length;
10
11        // If the number of occupied slots is higher than the number of elements, skip this combination
12        if (occupiedSlotsCount > numCount) {
13            continue;
14        }
15      
16        // Iterate over each position to check and update the dp state
17        for (let pos = 0; pos < slotMasks; ++pos) {
18            // Check if the current position is occupied in the combination mask
19            if (((mask >> pos) & 1) === 1) {
20                // Calculate the slot index by right-shifting `pos` by one and adding one (slot numbers are 1-indexed)
21                const slotIndex = (pos >> 1) + 1;
22                // Calculate the new mask value by turning the current position's bit off
23                const newMask = mask ^ (1 << pos);
24                // Calculates the AND sum and updates the dp state if this state is better
25                dp[mask] = Math.max(dp[mask], dp[newMask] + (nums[occupiedSlotsCount - 1] & slotIndex));
26            }
27        }
28    }
29
30    // Returns the maximum AND sum of all possible combinations
31    return Math.max(...dp);
32}
33
Not Sure What to Study? Take the 2-min Quiz

Which data structure is used to implement recursion?

Time and Space Complexity

Time Complexity

The given Python code implements a solution to find the maximum AND sum with a given list of numbers and a fixed number of slots in which these numbers can be placed. It uses dynamic programming with a bitmask to represent different states.

To analyze the time complexity:

  • For each state of the bitmask i, which ranges from 0 to (1 << m) - 1 (where m = numSlots * 2), we iterate through each bitmask j which goes from 0 to m - 1.
  • Within this loop, we perform a constant-time operation, namely the AND operation and comparison between integers.
  • The .bit_count() method is also constant time on average thanks to modern CPU operations (though it could be considered O(log(m)) in some cases, depending on the implementation)
  • The total number of states that we iterate over is 1 << m, and we perform up to m operations for each state.

Hence, the time complexity is O(m * 2^m) where m = numSlots << 1.

Space Complexity

Looking at the space complexity:

  • We utilize a list f of size 1 << m, which is the primary space consumption in the algorithm.
  • No additional data structures grow with respect to n or m, apart from constant space for variables.

Thus, the space complexity of the algorithm is O(2^m) where m = numSlots << 1.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Bitmask Introduction

Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«