Maximum Number of Groups Getting Fresh Donuts — Solution
Maximum Number of Groups Getting Fresh Donuts solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Groups Getting Fresh Donuts is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Bit Manipulation, Bitmask, Memoization
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A donut shop bakes donuts in batches of exactly batchSize, and it never starts a new batch until every donut of the current batch has been served. Groups of customers arrive: group i has groups[i] people, and all members of a group are served one after another before the next group begins. Every customer gets one donut.
A group is happy if its first customer receives a freshly baked donut — that is, the batch in progress had no donuts left over from earlier customers when this group started.
You may arrange the groups in any order. Return the maximum possible number of happy groups.
Example 1
Input: batchSize = 3, groups = [1,2,3,4,5,6]
Output: 4
Explanation: One good order is [6,2,4,5,1,3]: groups 6, 2, 4 and 1 each start on a fresh batch.
Example 2
Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6]
Output: 4
Example 3
Input: batchSize = 1, groups = [7,7,7]
Output: 3
Explanation: With batches of one donut, every group starts fresh.
Constraints
1 <= batchSize <= 91 <= groups.length <= 301 <= groups[i] <= 10^9
Hints for Maximum Number of Groups Getting Fresh Donuts
Hint 1
Only
groups[i] % batchSizematters. Groups whose size is a multiple ofbatchSizecan all go first, and each of them is happy.Hint 2
A group with remainder
rfollowed by one with remainderbatchSize - rbrings the leftover back to zero: greedily pair them up, each pair contributing one happy group.Hint 3
What remains is small: count how many groups of each remainder are left and search over those counts, where the leftover is fixed by which groups have been served. Memoise on the counts.
How to solve Maximum Number of Groups Getting Fresh Donuts
Reduce every group to its remainder modulo batchSize. The state of the arrangement is then just how many groups of each remainder are still waiting — the current leftover is determined by what has been served. Greedy pairing of complementary remainders shrinks that state space to a few thousand.
Approach
- Count
cnt[r]groups per remainder. Start withanswer = cnt[0](they go first, each happy). - For
r < batchSize - r, pairp = min(cnt[r], cnt[batchSize - r])groups: each pair adds 1. Forr == batchSize - r, pairs within the class addcnt[r] / 2. Remove the paired groups. - Encode the remaining counts as a mixed-radix index;
dp[u]is the most happy groups among the groups used in stateu. Iterate states in increasing order; the served sum modulobatchSizetells whether the next group is happy. - Return
answer + dp[all used].
Why it works
A group is happy exactly when the remainders served before it sum to 0 modulo batchSize, so the outcome depends only on the multiset of remainders served, which the count vector captures. Pairing complementary remainders is safe: in any arrangement, rearranging so each such pair is adjacent never loses a happy group, since a pair restores the leftover to zero and contributes one happy start. After pairing, at most one of each complementary pair of classes is non-empty, so the remaining state count is tiny.
Complexity
- Time —
O(S * batchSize) where S is the number of count vectors (a few thousand) - Space —
O(S)
Pitfalls
- Large group sizes (up to 10^9) only matter modulo
batchSize; never simulate donuts. - Remainder classes with
r == batchSize - rpair with themselves. - The first group served is always happy, even after the zero-remainder groups.
Reference solution
Python
from typing import List
def maxHappyGroups(batchSize: int, groups: List[int]) -> int:
b = batchSize
cnt = [0] * b
for g in groups:
cnt[g % b] += 1
ans = cnt[0]
for r in range(1, b):
s = b - r
if r < s:
p = min(cnt[r], cnt[s])
ans += p
cnt[r] -= p
cnt[s] -= p
elif r == s:
ans += cnt[r] // 2
cnt[r] %= 2
stride = [0] * b
total = 1
for r in range(1, b):
stride[r] = total
total *= cnt[r] + 1
dp = [0] * total
for idx in range(total):
used = [(idx // stride[r]) % (cnt[r] + 1) if r else 0 for r in range(b)]
happy = 1 if sum(used[r] * r for r in range(b)) % b == 0 else 0
cur = dp[idx] + happy
for r in range(1, b):
if used[r] < cnt[r] and cur > dp[idx + stride[r]]:
dp[idx + stride[r]] = cur
return ans + dp[total - 1]Java
public static int maxHappyGroups(int batchSize, int[] groups) {
int b = batchSize;
int[] cnt = new int[b];
for (int g : groups) cnt[g % b]++;
int ans = cnt[0];
for (int r = 1; r < b; r++) {
int s = b - r;
if (r < s) {
int p = Math.min(cnt[r], cnt[s]);
ans += p; cnt[r] -= p; cnt[s] -= p;
} else if (r == s) {
ans += cnt[r] / 2;
cnt[r] %= 2;
}
}
int[] stride = new int[b];
int total = 1;
for (int r = 1; r < b; r++) { stride[r] = total; total *= cnt[r] + 1; }
int[] dp = new int[total], used = new int[b];
for (int idx = 0; idx < total; idx++) {
int sum = 0;
for (int r = 1; r < b; r++) {
used[r] = (idx / stride[r]) % (cnt[r] + 1);
sum += used[r] * r;
}
int cur = dp[idx] + (sum % b == 0 ? 1 : 0);
for (int r = 1; r < b; r++) {
if (used[r] < cnt[r] && cur > dp[idx + stride[r]]) dp[idx + stride[r]] = cur;
}
}
return ans + dp[total - 1];
}C++
int maxHappyGroups(int batchSize, vector<int>& groups) {
int b = batchSize;
vector<int> cnt(b, 0);
for (int g : groups) cnt[g % b]++;
int ans = cnt[0];
for (int r = 1; r < b; r++) {
int s = b - r;
if (r < s) {
int p = min(cnt[r], cnt[s]);
ans += p; cnt[r] -= p; cnt[s] -= p;
} else if (r == s) {
ans += cnt[r] / 2;
cnt[r] %= 2;
}
}
vector<int> stride(b, 0), used(b, 0);
int total = 1;
for (int r = 1; r < b; r++) { stride[r] = total; total *= cnt[r] + 1; }
vector<int> dp(total, 0);
for (int idx = 0; idx < total; idx++) {
int sum = 0;
for (int r = 1; r < b; r++) {
used[r] = (idx / stride[r]) % (cnt[r] + 1);
sum += used[r] * r;
}
int cur = dp[idx] + (sum % b == 0 ? 1 : 0);
for (int r = 1; r < b; r++) {
if (used[r] < cnt[r] && cur > dp[idx + stride[r]]) dp[idx + stride[r]] = cur;
}
}
return ans + dp[total - 1];
}JavaScript
var maxHappyGroups = function(batchSize, groups) {
var b = batchSize, cnt = new Array(b).fill(0);
for (var i = 0; i < groups.length; i++) cnt[groups[i] % b]++;
var ans = cnt[0];
for (var r = 1; r < b; r++) {
var s = b - r;
if (r < s) {
var p = Math.min(cnt[r], cnt[s]);
ans += p; cnt[r] -= p; cnt[s] -= p;
} else if (r === s) {
ans += Math.floor(cnt[r] / 2);
cnt[r] %= 2;
}
}
var stride = new Array(b).fill(0), total = 1;
for (var r = 1; r < b; r++) { stride[r] = total; total *= cnt[r] + 1; }
var dp = new Array(total).fill(0), used = new Array(b).fill(0);
for (var idx = 0; idx < total; idx++) {
var sum = 0;
for (var r = 1; r < b; r++) {
used[r] = Math.floor(idx / stride[r]) % (cnt[r] + 1);
sum += used[r] * r;
}
var cur = dp[idx] + (sum % b === 0 ? 1 : 0);
for (var r = 1; r < b; r++) {
if (used[r] < cnt[r] && cur > dp[idx + stride[r]]) dp[idx + stride[r]] = cur;
}
}
return ans + dp[total - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming