1815. Maximum Number of Groups Getting Fresh Donuts
Problem Description
The goal in this problem is to optimize the happiness of groups visiting a donut shop. A donut shop bakes donuts in batches of a fixed size, batchSize. Groups of customers arrive one after another, and each group size is represented as an element in the groups array. For example, if groups is [3, 5, 1, 2], this means 4 groups of customers will visit the shop in this sequence, with respective group sizes of 3, 5, 1, and 2. Each customer from a group must be served a donut at the same time, and a group is defined as 'happy' if they all receive fresh donuts â no donuts left over from the previous group's batch.
Your task is to rearrange the groups in such a way that maximizes the number of happy groups. You are to return the maximum number of happy groups possible after doing any rearrangements necessary.
Intuition
The solution involves a bit of clever counting and dynamic programming to avoid redundant calculations. The intuition behind the solution is to classify and count the groups based on the remainder they leave when their size is divided by batchSize (groups[i] % batchSize). If the remainder is zero, then that group is automatically happy, as they will exactly finish a batch. For groups that do leave a remainder, we need to track not just how many groups leave the same remainder, but also the state of current leftover donuts when deciding to serve subsequent groups to maximize happiness.
We can represent the state with a bitmask, where for each remainder r, we assign it 5 bits (since 2^5 is more than enough to store count information) and bitwise shift into position r.
To navigate through all possible group arrangements efficiently, we use recursion with memoization (dfs function). At each state, we try serving a group with a remainder that, when added to the current leftover (modeled by mod), will not leave any leftover donuts (i.e., will complete a batch). Each recursive step, we attempt to serve a different remainder group by decreasing the count of that remainder in the state and adjusting the leftover. The result is the number of happy groups following the current group.
The dynamic programming approach, enhanced by memoization with the cache decorator, significantly reduces the number of recalculations by storing intermediate results. The dfs function takes the current state and 'mod' (the current leftover donuts) and returns the maximum number of happy groups that can follow.
Initially, all groups that don't leave a remainder when divided by batchSize are counted as happy (ans variable). The remaining groups are processed to form the initial state, and the recursive dfs function is called to find the maximum number of happy groups from the rearranged groups.
Learn more about Memoization, Dynamic Programming and Bitmask patterns.
Which type of traversal does breadth first search do?
Solution Approach
Our solution approach uses both recursion and dynamic programming with memoization, taking advantage of Python's @cache decorator for efficiency. The key is to combine counting, bitmasking, and depth-first search (DFS) to explore possible orderings that maximize the number of happy groups.
Let's break down the solution step by step to better understand the implementation:
-
Step 1: Initialization
First, we create variables to hold the overall state and the count of already happy groups. The state will be an integer (
state), and the initial count of happy groups (ans) is 0. -
Step 2: Count Happy Groups with no Remainder
We iterate over the
groupsarray to count the groups that will already be happy without rearrangement, i.e., those groups whose size is a multiple of thebatchSize(i % batchSize == 0). For each such group, we incrementanssince they are guaranteed to be happy. -
Step 3: Construct the Initial State
For the remaining groups that do leave a remainder, we construct a bitmask state. For each remainder
r(wherer = groups[i] % batchSize), we shift1left byr * 5bits and increment that part ofstate. This packs the remainders count compactly in a single integer. -
Step 4: The DFS Function
The
dfsfunction is at the heart of the solution. Given the current state and themod(number of donuts that would be left over), this function calculates the maximum number of additional happy groups that can be formed by serving the groups in the best possible order.Here's how the function works:
-
Base Case: If there are no more groups left to rearrange (i.e.,
stateis 0), return 0 because we can't make any more happy groups. -
Recursive Case: Loop through possible remainders
from 1 to batchSize - 1and check if there's a group available with that remainder (using bitwise operations to extract count information fromstate). If such a group exists, serve it:- Recurse with the new state (which has one less group of the current remainder) and the new modulus
mod, which accounts for the donuts that will be left over after serving this group. - Keep track of whether this group will be happy (i.e.,
mod == 0) and add this to the total from recursion. - Update the result
resto be the maximum of itself and the newly calculated total number of happy groups.
- Recurse with the new state (which has one less group of the current remainder) and the new modulus
The return value of the
dfsfunction is the maximum number of happy groups that can follow after serving a particular arrangement of the groups.Since computing
dfsis expensive and has overlapping subproblems, we apply memoization to cache results and reuse them when the same state recurs. -
-
Step 5: Compute Final Answer
After counting the groups that are already happy and preparing the initial state, we call
dfs(state, 0)to compute how many additional groups can be made happy by rearrangement.We then add the result from the DFS to
ansfor the final count of maximum happy groups and return it.
This combination of intelligent counting, bitmask to encode states, and memoized recursion builds up the solution to an otherwise intractable problem due to its combinatorial nature.
Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
Example Walkthrough
Let's walk through a small example to illustrate the solution approach. Assume we have a batchSize of 3 and the groups array is [1,2,3,4]. This means that every batch of donuts baked is made up of 3 donuts and 4 groups are visiting the shop with sizes of 1, 2, 3, and 4 respectively.
-
Step 1: Initialization
We initialize the
stateto 0 andanswhich counts the already happy groups to 0. -
Step 2: Count Happy Groups with no Remainder
The group of size
3does not leave a remainder when divided bybatchSize(3 % 3 == 0). Thus, we know this group will be automatically happy. We setans = 1. -
Step 3: Construct the Initial State
Now for the rest of the groups
[1, 2, 4], we consider their remainders when divided bybatchSize. Their remainders are[1, 2, 1]. We represent this state using a bitmask. The state integer will be updated as follows: we increment the state by1 << (1 * 5)for the first group with remainder 1,1 << (2 * 5)for the second group with remainder 2, and again by1 << (1 * 5)for the fourth group with remainder 1. The state now encodes the remainders count:state = 0b1000000100001. -
Step 4: The DFS Function
The
dfsfunction takes (state,mod) and tries all possible ways of serving the groups to maximize happiness. Starting withmod = 0(no leftover donuts), we explore states by serving groups with different remainders.Suppose we serve the group with remainder
1first. After serving,modbecomes 1, and we update the state to reflect one fewer group with remainder1. The new state becomes0b1000001. Sincemodwas 0 before serving, this group isn't happy.Next, if we serve the group with remainder
2,modwould become3(as 1 from the previous step + 2 from this group), which is a full batch. We update the state again, which becomes0b1, representing one fewer group with remainder2.As we just finished a batch with this serving, we mark this group as happy, increment the happy groups counter from this recursion branch, and continue exploring with the new
modof 0 (since the batch was completed).We continue in a similar fashion, exploring all combinations, memoizing the results for repeated states, and updating the result
resto keep track of the maximum number of happy groups. -
Step 5: Compute Final Answer
We call
dfs(state, 0)with thestatewe formed to get the number of additional groups we can make happy. Let's assume ourdfsreturns2for this example.We then add this to
answhere we already had1from the group of size3, yielding a final answer of3happy groups.
This small example demonstrates how we use the combination of counting, bitmasking the state, and applying a memoized depth-first search to efficiently calculate the maximum number of happy groups from the visiting groups to the donut shop.
Solution Implementation
1from functools import lru_cache
2from typing import List
3
4class Solution:
5 def max_happy_groups(self, batch_size: int, groups: List[int]) -> int:
6 # Use memoization to store results of subproblems
7 @lru_cache(maxsize=None)
8 def dfs(state, remaining):
9 max_happy = 0
10 is_happy_group = int(remaining == 0)
11
12 # Iterate through all possible group sizes (from 1 to batch_size-1)
13 for size in range(1, batch_size):
14 count = (state >> (size * 5)) & 31
15 # If there are groups of current size left, try taking one group out and continue DFS
16 if count:
17 next_state = state - (1 << (size * 5))
18 next_remaining = (remaining + size) % batch_size
19 happy_count = dfs(next_state, next_remaining)
20 # Update max_happy if the resulting configuration gives more happy groups
21 max_happy = max(max_happy, happy_count + is_happy_group)
22 return max_happy
23
24 # Initialize state to keep track of the number of groups of each size modulo batch_size
25 state = 0
26 # Start with initial max_happy groups where the group size is a multiple of batch_size
27 max_happy_groups = 0
28 for group_size in groups:
29 mod_group_size = group_size % batch_size
30 max_happy_groups += mod_group_size == 0
31 # If the group size is not a multiple of batch_size, encode it into state
32 if mod_group_size:
33 state += 1 << (mod_group_size * 5)
34
35 # Launch DFS to find the rest of the happy groups
36 max_happy_groups += dfs(state, 0)
37 return max_happy_groups
381import java.util.Map;
2import java.util.HashMap;
3
4class Solution {
5 // HashMap to memoize solutions of states
6 private Map<Long, Integer> memo = new HashMap<>();
7 private int batchSize;
8
9 public int maxHappyGroups(int batchSize, int[] groups) {
10 this.batchSize = batchSize;
11 int happyGroupsCount = 0; // Count of happy groups
12 long state = 0; // State representation of groups modulo batchSize
13 // Pre-processing: Count groups that are already happy (size % batchSize == 0)
14 for (int group : groups) {
15 int remainder = group % batchSize;
16 if (remainder == 0) {
17 happyGroupsCount++;
18 } else {
19 // Left-shift by 5 places for each remainder slot to represent groups in state bitmask
20 state += 1L << (remainder * 5);
21 }
22 }
23 // Recursive Depth-First Search (DFS) to find max happy groups
24 happyGroupsCount += dfs(state, 0);
25 return happyGroupsCount;
26 }
27
28 private int dfs(long state, int runningMod) {
29 // If the state has already been computed, return the stored result
30 if (memo.containsKey(state)) {
31 return memo.get(state);
32 }
33 int maxGroupsFromState = 0; // Max happy groups from current state
34 for (int i = 1; i < batchSize; ++i) {
35 // Check if groups with current modulo exist
36 if ((state >> (i * 5) & 31) != 0) {
37 // Recurse with the new state, removing one group of current modulo
38 int t = dfs(state - (1L << (i * 5)), (runningMod + i) % batchSize);
39 // If remaining modulo is 0, it can be a new happy group
40 maxGroupsFromState = Math.max(maxGroupsFromState, t + (runningMod == 0 ? 1 : 0));
41 }
42 }
43 memo.put(state, maxGroupsFromState); // Memoize the result
44 return maxGroupsFromState;
45 }
46}
471class Solution {
2public:
3 // Function to find the maximum number of happy groups.
4 int maxHappyGroups(int batchSize, vector<int>& groups) {
5 using ll = long long; // Alias for long long type as 'll'.
6 unordered_map<ll, int> memo; // Memoization for dynamic programming, stores state and result.
7
8 ll state = 0; // Bit representation of the state.
9 int numHappyGroups = 0; // Initialize number of happy groups to zero.
10
11 // Pre-process groups to count happy groups divisible by batchSize and to represent the remaining.
12 for (auto& groupSize : groups) {
13 int remainder = groupSize % batchSize;
14 numHappyGroups += remainder == 0; // Increment count if the group is already happy.
15 if (remainder) {
16 // Increment the state by setting the bits for the remainder count.
17 state += 1ll << (remainder * 5);
18 }
19 }
20
21 // Define the recursive function using dynamic programming to find maximum happy groups.
22 function<int(ll, int)> dfs = [&](ll currentState, int currentModulo) {
23 // Check if the result for the current state has already been computed.
24 if (memo.count(currentState)) {
25 return memo[currentState];
26 }
27 int maxGroups = 0; // Track the max groups for this state.
28 // Check if the current group can be happy.
29 int isNewGroupHappy = currentModulo == 0;
30
31 // Try different group sizes and update the states accordingly.
32 for (int i = 1; i < batchSize; ++i) {
33 if (currentState >> (i * 5) & 31) { // Check if this group size can be used.
34 // Recursively call dfs with the new state and modulo.
35 int temp = dfs(currentState - (1ll << (i * 5)), (currentModulo + i) % batchSize);
36 maxGroups = max(maxGroups, temp + isNewGroupHappy); // Update maxGroups.
37 }
38 }
39 // Save the result in memoization and return.
40 return memo[currentState] = maxGroups;
41 };
42
43 // Calculate the result starting from the state and 0 modulo.
44 numHappyGroups += dfs(state, 0);
45
46 // Return the final count of happy groups.
47 return numHappyGroups;
48 }
49};
501// Type alias for large integers.
2type ll = bigint;
3
4// Memoization map to store the dynamic programming states and their results.
5const memo: Map<ll, number> = new Map();
6
7// Variable to hold the number of happy groups.
8let numHappyGroups = 0;
9
10// Pre-process function to count happy groups divisible by batchSize and represent the remaining.
11function preprocessGroups(batchSize: number, groups: number[]): ll {
12 let state: ll = BigInt(0);
13
14 for (let groupSize of groups) {
15 let remainder = groupSize % batchSize;
16 numHappyGroups += remainder === 0 ? 1 : 0; // Increment count if the group is already happy.
17 if (remainder) {
18 // Increment the state by setting the bits for the remainder count.
19 state += BigInt(1) << (BigInt(remainder) * BigInt(5));
20 }
21 }
22 return state;
23}
24
25// Recursive function using dynamic programming to find maximum happy groups.
26function dfs(currentState: ll, currentModulo: number, batchSize: number): number {
27 // Check if the result for the current state has been computed.
28 if (memo.has(currentState)) {
29 return memo.get(currentState)!;
30 }
31
32 let maxGroups = 0; // Track the max groups for this state.
33 // Check if the current group can be happy.
34 let isNewGroupHappy = currentModulo === 0 ? 1 : 0;
35
36 // Iterate through different group sizes to update the states accordingly.
37 for (let i = 1; i < batchSize; ++i) {
38 if ((currentState >> (BigInt(i) * BigInt(5))) & BigInt(31)) {
39 // Recursively call dfs with the new state and modulo.
40 let temp = dfs(currentState - (BigInt(1) << (BigInt(i) * BigInt(5))), (currentModulo + i) % batchSize, batchSize);
41 maxGroups = Math.max(maxGroups, temp + isNewGroupHappy);
42 }
43 }
44 // Save the result in memoization map.
45 memo.set(currentState, maxGroups);
46
47 return maxGroups;
48}
49
50// Main function to find the maximum number of happy groups.
51function maxHappyGroups(batchSize: number, groups: number[]): number {
52 let state: ll = preprocessGroups(batchSize, groups);
53
54 // Calculate the result starting from the state and 0 modulo.
55 numHappyGroups += dfs(state, 0, batchSize);
56
57 // Return the final count of happy groups.
58 return numHappyGroups;
59}
60How does merge sort divide the problem into subproblems?
Time and Space Complexity
Time Complexity
The given Python code defines a recursive function that uses memoization for optimizing the solution to the problem of finding the maximum number of happy groups given batchSize and groups. Here's an analysis of the time complexity:
- The
dfsfunction uses a memoization decorator@cache, which ensures that each unique state-mod pair is only computed once. Thestatevariable is a bitmask that holds up tobatchSizedifferent group sizes, each represented by a 5-bit number. Hence, there are2^(5*batchSize)possible states. - For each state,
dfsiterates overbatchSize - 1possibilities, since it skips the0group size. - The recursion depth is at most
batchSize.
Combining all the above factors, the worst-case time complexity is O(batchSize * 2^(5*batchSize)).
Space Complexity
The space complexity mainly comes from two parts:
- The space for the cache used by
dfs. Since it needs to cache each unique state-mod pair, and there are2^(5*batchSize)possible states andbatchSizedifferent mod values, the space complexity for the memoization cache isO(batchSize * 2^(5*batchSize)). - The stack space due to recursive calls which would be
O(batchSize), since that's the deepest the recursion can go.
Overall, the space complexity is dominated by the cache used for memoization, resulting in O(batchSize * 2^(5*batchSize)).
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
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 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
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.