There is a donuts shop that bakes donuts in batches of batchSize. They have a rule where they must serve all of the donuts of a batch before serving any donuts of the next batch. You are given an integer batchSize and an integer array groups, where groups[i] denotes that there is a group of groups[i] customers that will visit the shop. Each customer will get exactly one donut.
When a group visits the shop, all customers of the group must be served before serving any of the following groups. A group will be happy if they all get fresh donuts. That is, the first customer of the group does not receive a donut that was left over from the previous group.
You can freely rearrange the ordering of the groups. Return the maximum possible number of happy groups after rearranging the groups.
Example 1:
Input: batchSize = 3, groups = [1,2,3,4,5,6] Output: 4 Explanation: You can arrange the groups as [6,2,4,5,1,3]. Then the 1st, 2nd, 4th, and 6th groups will be happy.
Example 2:
Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6] Output: 4
Constraints:
1 <= batchSize <= 91 <= groups.length <= 301 <= groups[i] <= 109Problem Overview: You run a donut shop where donuts are baked in fixed batch sizes. Each arriving group wants fresh donuts, meaning the first donut they receive must come from a new batch. The task is to reorder groups so the maximum number of them get fresh donuts.
The key observation: only the remainder groupSize % batchSize affects whether a group starts a fresh batch. This transforms the problem from large numbers into a frequency counting and state optimization problem.
Approach 1: Greedy Approach with Modulo Counting (O(n + batchSize²) time, O(batchSize) space)
Start by computing the remainder of every group size with batchSize. Groups with remainder 0 always start a fresh batch, so they directly increase the answer. For the rest, count frequencies of remainders using an array. Pair complementary remainders such that r + (batchSize - r) = batchSize. Each pair forms a complete batch and guarantees another fresh group.
For example, remainder 1 pairs with batchSize - 1. Greedily match these counts and reduce the remaining groups. This step eliminates obvious combinations quickly and significantly shrinks the search space. The greedy preprocessing works well because complementary pairs always produce full batches without affecting future decisions.
Approach 2: Dynamic Programming with Memoization (O(batchSize * states) time, exponential states pruned, O(states) space)
After greedy pairing, some remainder groups still remain. Their order determines how leftovers accumulate. Model this as a state search using dynamic programming with memoization. The state tracks the current leftover donuts and the remaining count of each remainder.
Represent the remainder counts compactly using bit manipulation or a bitmask-style encoded integer. Each recursive step chooses a remainder group, updates the leftover modulo batchSize, and continues. If the leftover becomes zero before serving a group, that group gets fresh donuts and increases the score.
Memoization caches results for previously seen states so identical remainder configurations are not recomputed. The search space is large in theory but small in practice because batchSize ≤ 9 and counts are limited. This DP formulation explores all valid permutations while pruning redundant states.
Recommended for interviews: Start by explaining the greedy remainder pairing since it demonstrates understanding of modular arithmetic and batching behavior. Then transition to the memoized DP that encodes remainder frequencies as state. Interviewers typically expect the DP optimization because brute force permutations are infeasible, and the memoized state search shows strong algorithmic reasoning.
This approach utilizes the property of modulo arithmetic to rearrange the groups such that the total number of leftover donuts between batch servings is minimized. By counting how many groups have a particular remainder when divided by batchSize, we can decide the optimal order to serve the groups for maximizing the number of happy groups.
The solution uses a modulo count strategy to pair groups. It counts how many groups give each possible remainder when divided by the batch size. Groups with complementary remainders (like 1 and batchSize-1) get paired to form a happy group. Special handling is applied for pairs with the same remainder.
Time Complexity: O(n), where n is the length of the groups array because we iterate through the groups once to count remainders.
Space Complexity: O(batchSize) for the count array.
This approach uses a recursive function combined with memoization to explore all possible arrangements of groups. We use dynamic programming to store results of previously computed states to avoid redundant calculations.
This C solution uses a recursive utility function to check all combinations of group arrangements, utilizing a bitmask to track which remainders have been used. Memoization is employed for efficiency to store previously calculated states.
Time Complexity: O(2^batchSize * batchSize), which arises from exploring all subset combinations.
Space Complexity: O(2^batchSize * batchSize) for the memoization table.
The problem actually asks us to find an arrangement order that maximizes the number of groups whose prefix sum (referring to "number of people" here) modulo batchSize equals 0. Therefore, we can divide all customers into two categories:
batchSize. These customers will not affect the donuts of the next group of customers. We can greedily arrange these groups of customers first, so these groups of customers will be happy. The "initial answer" is the number of these groups.batchSize. The arrangement order of these customers will affect the donuts of the next group of customers. We can take the modulo batchSize for the number of people v in each group here, and the remainders form a set. The range of element values in the set is [1,2...,batchSize-1]. The maximum length of the groups array is 30, so the maximum number of each remainder does not exceed 30. We can use 5 binary bits to represent the quantity of a remainder, and the maximum batchSize is 9, so the total number of binary bits required to represent these remainders and their quantities is 5times (9-1)=40. We can use a 64-bit integer state to represent it.Next, we design a function dfs(state, mod), which represents the number of groups that can be happy when the arrangement state is state and the current prefix remainder is mod. Then our "initial answer" plus dfs(state, 0) is the final answer.
The implementation logic of the function dfs(state, mod) is as follows:
We enumerate each remainder i from 1 to batchSize-1. If the quantity of the remainder i is not 0, we can subtract 1 from the quantity of the remainder i, add i to the current prefix remainder and take modulo batchSize, then recursively call the function dfs to find the optimal solution of the sub-state, and take the maximum value. Finally, check whether mod is 0. If it is 0, we return after adding 1 to the maximum value, otherwise we directly return the maximum value.
During the process, we can use memorized search to avoid repeated calculation of states.
The time complexity does not exceed O(10^7), and the space complexity does not exceed O(10^6).
Python
| Approach | Complexity |
|---|---|
| Greedy Approach with Modulo Counting | Time Complexity: O(n), where n is the length of the groups array because we iterate through the groups once to count remainders. |
| Dynamic Programming with Memoization | Time Complexity: O(2^batchSize * batchSize), which arises from exploring all subset combinations. |
| Greedy + State Compression + Memorized Search | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Modulo Counting | O(n + batchSize²) | O(batchSize) | Initial optimization to pair complementary remainders and reduce the search space |
| Dynamic Programming with Memoization | O(batchSize * states) | O(states) | General case where leftover remainder groups require exploring optimal ordering |
花花酱 LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts - 刷题找工作 EP391 • Hua Hua • 2,514 views views
Watch 7 more video solutions →Practice Maximum Number of Groups Getting Fresh Donuts with our built-in code editor and test cases.
Practice on FleetCode