Skip to main content
Talentd

Maximum Number of Groups Getting Fresh Donuts - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationMemoization23 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 9
  • 1 <= groups.length <= 30
  • 1 <= groups[i] <= 109

Approach Overview

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

Approach 1: Greedy Approach with Modulo Counting

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming with Memoization

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^batchSize * batchSize), which arises from exploring all subset combinations.
Space Complexity: O(2^batchSize * batchSize) for the memoization table.

Try this approach in the editor →

Approach 3: Greedy + State Compression + Memorized Search

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:

  • Customers whose number is a multiple of 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.
  • Customers whose number is not a multiple of 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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 4: Default Approach

Code

Python

Python

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(batchSize) for the count array.

Dynamic Programming with Memoization

Time Complexity: O(2^batchSize * batchSize), which arises from exploring all subset combinations.
Space Complexity: O(2^batchSize * batchSize) for the memoization table.

Greedy + State Compression + Memorized Search—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Modulo CountingO(n + batchSize²)O(batchSize)Initial optimization to pair complementary remainders and reduce the search space
Dynamic Programming with MemoizationO(batchSize * states)O(states)General case where leftover remainder groups require exploring optimal ordering

Video Solution

花花酱 LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts - 刷题找工作 EP391 • Hua Hua • 2,518 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Maximum Number of Groups Getting Fresh Donuts easy or hard?
Maximum Number of Groups Getting Fresh Donuts is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that only remainders matter, applying greedy reductions, and designing a memoized dynamic programming state that encodes remaining group counts efficiently.
Maximum Number of Groups Getting Fresh Donuts Python/Java solution
Implementations typically compute remainder frequencies, apply greedy pairing, then run a recursive DP with memoization. Python solutions often use dictionaries or functools.lru_cache for caching states, while Java implementations use HashMap for memoization. Both follow the same remainder-count state transition logic.
How to solve Maximum Number of Groups Getting Fresh Donuts in O(n)?
A pure O(n) solution is not possible because the ordering of remaining groups affects the outcome. However, you can reduce the problem significantly in O(n) time by counting remainders and greedily pairing complementary values. After that reduction, a memoized DP searches the remaining configurations efficiently.
What is the best approach for Maximum Number of Groups Getting Fresh Donuts?
The optimal strategy combines greedy remainder pairing with dynamic programming and memoization. First count group remainders modulo batchSize and greedily pair complementary remainders that sum to batchSize. For the remaining groups, use DP with memoization to explore orders of serving groups while tracking leftover donuts. This avoids brute force permutations and keeps the state space manageable.
Is Maximum Number of Groups Getting Fresh Donuts asked at Google/Amazon/Meta?
This problem appears in interview preparation sets for companies such as Google and other large tech firms because it tests modular arithmetic, dynamic programming, and state compression. The combination of greedy preprocessing and DP with memoization reflects the type of optimization problems commonly asked in senior interviews.
What data structure is used in Maximum Number of Groups Getting Fresh Donuts?
The solution primarily uses an array to store counts of group remainders modulo batchSize. The optimized version also uses memoization with a hash map or dictionary to cache DP states. Bitmask-style state encoding or bit manipulation helps compress remainder counts into a compact representation.
What is the time complexity of Maximum Number of Groups Getting Fresh Donuts?
The greedy preprocessing runs in O(n + batchSize²) time. The dynamic programming stage explores encoded remainder states with memoization, giving roughly O(batchSize * states) time where states represent unique remainder frequency combinations. Space complexity is O(states) for the memoization cache.

Ready to solve this problem?

Practice Maximum Number of Groups Getting Fresh Donuts with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays