Maximum Number of Groups Getting Fresh Donuts solution and explanation
Google
6 more videos on this problem
花花酱 LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts - 刷题找工作 EP391Hua Hua · 21:58 · 2K views
LeetCode 1815. Maximum Number of Groups Getting Fresh DonutsHappy Coding · 23:20 · 1K views
1815. Maximum Number of Groups Getting Fresh Donuts (Leetcode Hard)Programming Live with Larry · 53:36 · 490 views
【每日一题】1815. Maximum Number of Groups Getting Fresh Donuts, 4/6/2021Huifeng Guan · 33:23 · 471 views
LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts | Biweekly Contest 49宰相小甘罗 · 9:06 · 338 views
Leetcode 1815. Maximum Number of Groups Getting Fresh DonutsFearless Learner · 5:33 · 243 views
LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts 中文 | Biweekly Contest 49宰相小甘罗 · 7:43 · 212 views
The problem
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] <= 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.
def maxHappyGroups(batchSize, groups):
count = [0] * batchSize
for group in groups:
count[group % batchSize] += 1
result = count[0]
for i in range(1, (batchSize + 1) // 2):
if i != batchSize - i:
result += min(count[i], count[batchSize - i])
else:
result += count[i] // 2
return result
print(maxHappyGroups(3, [1, 2, 3, 4, 5, 6])) # Output: 4import java.util.*;
public class Main {
public static int maxHappyGroups(int batchSize, int[] groups) {
int[] count = new int[batchSize];
for (int group : groups) {
count[group % batchSize]++;
}
int result = count[0];
for (int i = 1; i <= batchSize / 2; i++) {
if (i != batchSize - i) {
result += Math.min(count[i], count[batchSize - i]);
} else {
result += count[i] / 2;
}
}
return result;
}
public static void main(String[] args) {
int[] groups = {1, 2, 3, 4, 5, 6};
int batchSize = 3;
System.out.println(maxHappyGroups(batchSize, groups)); // Output: 4
}
}#include <vector>
#include <unordered_map>
using namespace std;
int maxHappyGroups(int batchSize, const vector<int>& groups) {
vector<int> count(batchSize, 0);
for (int group : groups) {
count[group % batchSize]++;
}
int result = count[0];
for (int i = 1; i <= batchSize / 2; ++i) {
if (i != batchSize - i) {
result += min(count[i], count[batchSize - i]);
} else {
result += count[i] / 2;
}
}
return result;
}
int main() {
vector<int> groups = {1, 2, 3, 4, 5, 6};
int batchSize = 3;
int result = maxHappyGroups(batchSize, groups);
printf("%d\n", result);
return 0;
}function maxHappyGroups(batchSize, groups) {
let count = Array(batchSize).fill(0);
for (let group of groups) {
count[group % batchSize]++;
}
let result = count[0];
for (let i = 1; i <= batchSize / 2; i++) {
if (i != batchSize - i) {
result += Math.min(count[i], count[batchSize - i]);
} else {
result += Math.floor(count[i] / 2);
}
}
return result;
}
console.log(maxHappyGroups(3, [1, 2, 3, 4, 5, 6])); // Output: 4#include <stdio.h>
int maxHappyGroups(int batchSize, int* groups, int groupsSize) {
int count[10] = {0};
for (int i = 0; i < groupsSize; i++) {
count[groups[i] % batchSize]++;
}
int result = count[0];
for (int i = 1; i <= batchSize / 2; i++) {
if (i != batchSize - i) {
int pairedGroups = count[i] < count[batchSize - i] ? count[i] : count[batchSize - i];
result += pairedGroups;
} else {
result += count[i] / 2;
}
}
return result;
}
int main() {
int groups[] = {1, 2, 3, 4, 5, 6};
int batchSize = 3;
int result = maxHappyGroups(batchSize, groups, sizeof(groups)/sizeof(groups[0]));
printf("%d\n", result);
return 0;
}using System;
public class Program {
public static int MaxHappyGroups(int batchSize, int[] groups) {
int[] count = new int[batchSize];
foreach (int group in groups) {
count[group % batchSize]++;
}
int result = count[0];
for (int i = 1; i <= batchSize / 2; i++) {
if (i != batchSize - i) {
result += Math.Min(count[i], count[batchSize - i]);
} else {
result += count[i] / 2;
}
}
return result;
}
public static void Main(string[] args) {
int[] groups = {1, 2, 3, 4, 5, 6};
int batchSize = 3;
Console.WriteLine(MaxHappyGroups(batchSize, groups)); // Output: 4
}
}The Python solution defines a modulo frequency counter to determine how many full groups of a batchSize can be formed by combining groups with complementary remainders.
Time Complexity: O(n), where n is the total number of groups.
Space Complexity: O(batchSize), the space needed to maintain the list of remainders.
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.
def recurse(count, mask, batchSize, dp):
if dp[mask] != -1:
return dp[mask]
max_happy = 0
for i in range(batchSize):
if count[i] > 0:
count[i] -= 1
next_mask = mask | (1 << i)
max_happy = max(max_happy, recurse(count, next_mask, batchSize, dp))
count[i] += 1
dp[mask] = max_happy
return max_happy
def maxHappyGroups(batchSize, groups):
count = [0] * batchSize
for group in groups:
count[group % batchSize] += 1
dp = [-1] * (1 << (batchSize - 1))
return recurse(count, 0, batchSize, dp)
print(maxHappyGroups(4, [1, 3, 2, 5, 2, 2, 1, 6])) # Output: 4import java.util.*;
public class Main {
public static int recurse(int[] count, int mask, int batchSize, int[][] dp) {
if (dp[mask][batchSize] != -1) {
return dp[mask][batchSize];
}
int answer = 0;
for (int i = 0; i < batchSize; ++i) {
if (count[i] > 0) {
--count[i];
int nextMask = mask | (1 << i);
answer = Math.max(answer, recurse(count, nextMask, batchSize, dp));
count[i]++;
}
}
dp[mask][batchSize] = answer;
return answer;
}
public static int maxHappyGroups(int batchSize, int[] groups) {
int count[] = new int[batchSize];
for (int group : groups) {
count[group % batchSize]++;
}
int[][] dp = new int[1 << (batchSize - 1)][batchSize];
for (int[] d : dp) Arrays.fill(d, -1);
return recurse(count, 0, batchSize, dp);
}
public static void main(String[] args) {
int[] groups = {1, 3, 2, 5, 2, 2, 1, 6};
int batchSize = 4;
System.out.println(maxHappyGroups(batchSize, groups)); // Output: 4
}
}#include <vector>
#include <unordered_map>
using namespace std;
int recurse(vector<int>& count, int mask, int batchSize, vector<vector<int>>& dp) {
if (dp[mask] != -1) {
return dp[mask];
}
int answer = 0;
for (int i = 0; i < batchSize; ++i) {
if (count[i] > 0) {
--count[i];
int next_mask = mask | (1 << i);
answer = max(answer, recurse(count, next_mask, batchSize, dp));
++count[i];
}
}
dp[mask] = answer;
return answer;
}
int maxHappyGroups(int batchSize, const vector<int>& groups) {
vector<int> count(batchSize, 0);
for (int group : groups) {
count[group % batchSize]++;
}
vector<vector<int>> dp(1 << (batchSize - 1), vector<int>(-1));
return recurse(count, 0, batchSize, dp);
}
int main() {
vector<int> groups = {1, 3, 2, 5, 2, 2, 1, 6};
int batchSize = 4;
int result = maxHappyGroups(batchSize, groups);
printf("%d\n", result);
return 0;
}function recurse(count, mask, batchSize, dp) {
if (dp[mask] !== -1) return dp[mask];
let maxHappy = 0;
for (let i = 0; i < batchSize; i++) {
if (count[i] > 0) {
count[i]--;
let nextMask = mask | (1 << i);
maxHappy = Math.max(maxHappy, recurse(count, nextMask, batchSize, dp));
count[i]++;
}
}
dp[mask] = maxHappy;
return maxHappy;
}
function maxHappyGroups(batchSize, groups) {
let count = Array(batchSize).fill(0);
for (let group of groups) {
count[group % batchSize]++;
}
let dp = new Array(1 << (batchSize - 1)).fill(-1);
return recurse(count, 0, batchSize, dp);
}
console.log(maxHappyGroups(4, [1, 3, 2, 5, 2, 2, 1, 6])); // Output: 4#include <stdio.h>
#include <string.h>
#define MAX_BATCH 9
#define MAX_GROUPS 30
#define INVALID -1
int dp[1 << MAX_BATCH][MAX_BATCH];
int maxHappyGroupsUtil(int batchSize, int* count, int mask, int remainder) {
if (dp[mask][remainder] != INVALID) {
return dp[mask][remainder];
}
int maxHappy = 0;
for (int i = 0; i < batchSize; ++i) {
if (((mask >> i) & 1) && count[i] > 0) {
count[i]--;
maxHappy = count[i] + ((remainder + i) % batchSize == 0);
maxHappy = maxHappyGroupsUtil(batchSize, count, mask | (1 << i), (remainder + i) % batchSize);
count[i]++;
}
}
dp[mask][remainder] = maxHappy;
return maxHappy;
}
int maxHappyGroups(int batchSize, int* groups, int groupsSize) {
int count[MAX_BATCH] = {0};
for (int i = 0; i < groupsSize; ++i) {
count[groups[i] % batchSize]++;
}
memset(dp, INVALID, sizeof(dp));
return maxHappyGroupsUtil(batchSize, count, 1, 0);
}
int main() {
int groups[] = {1, 3, 2, 5, 2, 2, 1, 6};
int batchSize = 4;
int result = maxHappyGroups(batchSize, groups, sizeof(groups)/sizeof(groups[0]));
printf("%d\n", result);
return 0;
}using System;
public class Program {
static int Recurse(int[] count, int mask, int batchSize, int[][] dp) {
if (dp[mask][batchSize] != -1) {
return dp[mask][batchSize];
}
int maxHappy = 0;
for (int i = 0; i < batchSize; ++i) {
if (count[i] > 0) {
count[i]--;
int nextMask = mask | (1 << i);
maxHappy = Math.Max(maxHappy, Recurse(count, nextMask, batchSize, dp));
count[i]++;
}
}
dp[mask][batchSize] = maxHappy;
return maxHappy;
}
public static int MaxHappyGroups(int batchSize, int[] groups) {
int[] count = new int[batchSize];
foreach (int group in groups) {
count[group % batchSize]++;
}
int[][] dp = new int[1 << (batchSize - 1)][];
for (int i = 0; i < dp.Length; i++) {
dp[i] = new int[batchSize];
Array.Fill(dp[i], -1);
}
return Recurse(count, 0, batchSize, dp);
}
public static void Main(string[] args) {
int[] groups = {1, 3, 2, 5, 2, 2, 1, 6};
int batchSize = 4;
Console.WriteLine(MaxHappyGroups(batchSize, groups)); // Output: 4
}
}The Python version utilizes a recursive function with memoization for efficient computation, ensuring all different permutations are considered by embedding state tracking within a bitmask.
Time Complexity: O(2^batchSize * batchSize), needed due to the exploration of subset permutations.
Space Complexity: O(2^batchSize * batchSize), a requirement for the memoization table.
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 modulobatchSizefor the number of peoplevin 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 thegroupsarray is30, so the maximum number of each remainder does not exceed30. We can use5binary bits to represent the quantity of a remainder, and the maximumbatchSizeis9, so the total number of binary bits required to represent these remainders and their quantities is5times (9-1)=40. We can use a64-bit integerstateto 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).
func maxHappyGroups(batchSize int, groups []int) (ans int) {
state := 0
for _, v := range groups {
i := v % batchSize
if i == 0 {
ans++
} else {
state += 1 << (i * 5)
}
}
f := map[int]int{}
var dfs func(int, int) int
dfs = func(state, mod int) int {
if v, ok := f[state]; ok {
return v
}
res := 0
x := 0
if mod == 0 {
x = 1
}
for i := 1; i < batchSize; i++ {
if state>>(i*5)&31 != 0 {
t := dfs(state-1<<(i*5), (mod+i)%batchSize)
res = max(res, t+x)
}
}
f[state] = res
return res
}
ans += dfs(state, 0)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Modulo Counting | Time Complexity: O(n), where n is the total number of groups. |
| Dynamic Programming with Memoization | Time Complexity: O(2^batchSize * batchSize), needed due to the exploration of subset permutations. |
| Greedy + State Compression + Memorized Search | – |
Complexity analysis
| 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 |
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.