Maximum Number of Groups Getting Fresh Donuts

Maximum Number of Groups Getting Fresh Donuts

What is this problem about?

The Maximum Number of Groups Getting Fresh Donuts coding problem gives you groups of people arriving at a donut shop (represented by group sizes) and a batch size b. Each new batch of b donuts is made fresh. A group is "happy" if they arrive when a new batch has just started (i.e., the cumulative people so far before this group is a multiple of b). Arrange the groups in any order to maximize the number of happy groups.

Why is this asked in interviews?

Google uses this problem because it requires bitmask DP with memoization on a state space that encodes the "excess" of each group size modulo b. Brute-force permutation enumeration is O(n!), far too slow. The key insight is that only the remainders modulo b matter for determining happiness, and the count of each remainder value is the relevant state. This reduces to a small bitmask DP.

Algorithmic pattern used

Bitmask DP with memoization: First, groups whose size is divisible by b always make a new happy group — count them separately. For remaining groups, only their sizes mod b matter. Represent the "inventory" of each non-zero remainder (1 to b-1) as a bitmask state. DP over this state, tracking the current running sum mod b, and deciding which group to place next. Groups with complementary remainders (summing to b) pair up perfectly. The state space is bounded by the product of counts, manageable with memoization.

Example explanation

Groups: [1, 2, 3, 4, 5, 6], batch size b=3.

• Groups divisible by 3: [3, 6] → 2 happy groups automatically.
• Remaining: [1, 2, 4, 5] → remainders [1, 2, 1, 2].
• Pair up: remainder 1 and remainder 2 sum to 3 = b. Pairs: (1,2) and (1,2) → each pair makes the second group happy.
• Total happy = 2 (divisible) + 2 (paired) + 1 (the first in each pair, if it starts fresh) → depends on ordering. Best arrangement gives 4.

Common mistakes candidates make

• Not counting divisible-by-b groups separately: These always generate fresh starts and should be handled as free happy groups.
• Treating group sizes, not remainders, as state: The full size space is too large; only sizes mod b matter.
• Missing the complementary pairing optimization: Pairs of groups with remainders summing to b can always be arranged to generate one happy group per pair.

Interview preparation tip

For the Array Bitmask Memoization Bit Manipulation Dynamic Programming interview pattern, recognize that when only remainders modulo b matter and b is small, group by remainder and use bitmask DP over remainder counts. This "group by modular equivalence then bitmask DP" pattern appears in several hard interview problems involving scheduling and grouping.