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.
| 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. |
| 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