Maximum Number of Groups Getting Fresh Donuts: DP with Remainder States

You run a donut shop. Donuts come in batches of batchSize, and customers arrive in groups. When a group arrives, they are served from the current batch. If the leftover donuts from previous groups happen to be zero, that group gets a "fresh" start and is happy. You can choose the order in which groups are served. Given batchSize and an array groups where groups[i] is the size of the i-th group, find the maximum number of happy groups.

This is LeetCode 1815: Maximum Number of Groups Getting Fresh Donuts, and it is a great problem for learning how to combine greedy remainder analysis with dynamic programming on compact state representations.

Why this problem matters

At first glance, this looks like a brute-force permutation problem: try every ordering and count happy groups. But with up to 30 groups, that is far too many permutations. The key realization is that only the remainder of each group size modulo batchSize matters, not the actual group size. Two groups of size 7 and size 13 with batchSize = 3 are interchangeable because 7 % 3 == 1 and 13 % 3 == 1. This collapses the problem from permuting individual groups to tracking counts of each remainder.

Once you see the remainder structure, you can apply greedy pairing for the easy cases and DP for the rest. This combination of greedy preprocessing and DP on a small state space is a pattern you will encounter in many optimization problems.

The approach

The algorithm has three phases:

Phase 1: Count remainders. Replace each group size with group_size % batchSize. Groups with remainder 0 are always happy regardless of when they are served, because they consume a perfect number of batches. Count them and set them aside.

Phase 2: Pair complementary remainders. If remainder r and remainder batchSize - r are both present, you can place them back to back. The first one in the pair changes the leftover to r, and the second one resets it to 0. This means the group after the pair starts fresh. Each such pair contributes one happy group. Handle the special case where r == batchSize - r (this only happens when batchSize is even and r == batchSize / 2) by pairing them with themselves.

Phase 3: DP on remaining groups. After greedy pairing, some remainder counts may still be nonzero. For example, with batchSize = 5 you might have three groups with remainder 2 and one with remainder 3. You paired one of each, leaving two remainder-2 groups. Now you need DP. The state is (current_leftover, tuple_of_remaining_counts). For each state, try serving any available remainder, check if the current leftover is 0 (meaning this group is happy), update the leftover, and recurse. Memoize on the state tuple.

The solution

from functools import lru_cache

def max_happy_groups(batch_size: int, groups: list[int]) -> int:
    remainders = [0] * batch_size
    for g in groups:
        remainders[g % batch_size] += 1

    result = remainders[0]
    remainders[0] = 0

    for r in range(1, batch_size):
        comp = batch_size - r
        if r == comp:
            result += remainders[r] // 2
            remainders[r] %= 2
        elif r < comp and remainders[comp] > 0:
            pairs = min(remainders[r], remainders[comp])
            result += pairs
            remainders[r] -= pairs
            remainders[comp] -= pairs

    @lru_cache(maxsize=None)
    def dp(left_over: int, rem_tuple: tuple) -> int:
        rem = list(rem_tuple)
        best = 0
        for i in range(1, batch_size):
            if rem[i] == 0:
                continue
            rem[i] -= 1
            happy = 1 if left_over == 0 else 0
            new_left = (left_over + i) % batch_size
            happy += dp(new_left, tuple(rem))
            best = max(best, happy)
            rem[i] += 1
        return best

    result += dp(0, tuple(remainders))
    return result

Let's walk through what each piece does.

The first loop computes the remainder of every group size modulo batch_size and stores the counts. This is the core insight: two groups with the same remainder are identical from the algorithm's perspective.

Next, remainders[0] groups are added directly to result because they always start happy. Then we zero out that count since they are handled.

The greedy pairing loop iterates through remainders from 1 to batch_size - 1. For each r, its complement is batch_size - r. When r equals its complement (the even batchSize midpoint), we can pair remainder-r groups with each other, using integer division. Otherwise, we pair r with comp and subtract the matched pairs from both counts. The r < comp check ensures we only process each pair once.

The dp function handles whatever remains after greedy pairing. It takes the current leftover (how many donuts are sitting unserved from previous batches, mod batchSize) and a tuple of remainder counts. For each available remainder i, it tries serving that group next. If left_over == 0, that group gets a fresh start and earns a happy point. The new leftover becomes (left_over + i) % batch_size. The function returns the maximum happy count achievable from this state onward. Memoization via lru_cache ensures each unique state is computed only once.

Visual walkthrough

Let's trace through the algorithm with batchSize = 3 and groups = [1, 2, 3, 4, 5, 6].

In this example, greedy pairing handles everything. But when counts are unbalanced (say batchSize = 5 with groups [2, 2, 2, 3, 3, 3]), the DP phase picks up the slack by exploring the best ordering of leftover groups.

Complexity analysis

Time for the DP approach depends on the number of distinct states. The leftover can take batchSize values (0 through batchSize - 1), and the remainder tuple has at most batchSize - 1 entries, each bounded by the number of groups with that remainder. After greedy pairing, these counts are small. In the worst case, the state space is O(batchSize * product of remaining counts), which is manageable given batchSize is at most 9.

Space is proportional to the number of memoized states, which matches the time bound. The lru_cache stores one entry per unique (left_over, rem_tuple) pair.

The building blocks

1. Remainder arithmetic for grouping

The pattern of reducing values to their remainders to collapse equivalent items:

remainders = [0] * batch_size
for g in groups:
    remainders[g % batch_size] += 1

This is the same idea behind problems like Coin Change and Subarray Sum Equals K. When the only thing that matters is the remainder after division, you can bucket items by remainder and work with counts instead of individual values. You will see this pattern whenever a problem involves divisibility, cyclic behavior, or modular arithmetic.

2. DP with tuple state and memoization

The pattern of using a tuple of counts as the DP state with lru_cache:

@lru_cache(maxsize=None)
def dp(left_over: int, rem_tuple: tuple) -> int:
    rem = list(rem_tuple)
    for i in range(1, batch_size):
        if rem[i] == 0:
            continue
        rem[i] -= 1
        val = (1 if left_over == 0 else 0) + dp((left_over + i) % batch_size, tuple(rem))
        rem[i] += 1

When the DP state is a collection of counts rather than a single index, you can represent it as a tuple for hashing. This lets you use Python's lru_cache directly. You will encounter this approach in problems like Partition Equal Subset Sum (where the state is a remaining target) and other subset/multiset optimization problems where the "which items are left" state needs to be hashable.

Edge cases

Before submitting, think through these scenarios:

• All groups are multiples of batchSize: every remainder is 0. Every group is happy. Return len(groups).
• batchSize is 1: every group consumes a whole number of batches (since anything mod 1 is 0). Every group is happy. Return len(groups).
• Single group: the first group always starts fresh. Return 1.
• All groups have the same non-zero remainder: no complementary pairing is possible. The first group in the ordering starts fresh (leftover is 0), and the DP figures out if any subsequent groups can also land on a fresh start by accumulating remainders that sum to a multiple of batchSize.

From understanding to recall

You have seen how this problem breaks into three clean phases: remainder counting, greedy pairing, and DP on the leftover state. The concept is satisfying once you understand it. But writing it correctly under pressure is a different story.

The tricky parts are the greedy pairing loop (handling the r == comp case, making sure you only process each pair once) and the DP state design (converting a list of counts to a tuple for memoization, correctly tracking the leftover). These are not hard ideas, but they are easy to get wrong when you are writing from scratch in an interview.

Spaced repetition is how you make these patterns automatic. You practice the remainder-counting setup, the complementary pairing logic, and the tuple-state DP independently at increasing intervals. After a few rounds, you see "maximize some count by reordering with modular constraints" and the entire structure flows out without hesitation.

Related posts

• Coin Change - Classic DP problem where remainder and divisibility thinking helps you reason about reachable states
• Partition Equal Subset Sum - DP on subset sums with a target, teaching the pattern of compact state representation for subset problems
• Combination Sum IV - DP counting the number of ways to reach a target sum, reinforcing the "track what remains" approach

CodeBricks breaks Maximum Number of Groups Getting Fresh Donuts into its remainder-grouping and tuple-state DP building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a DP problem with modular structure shows up in your interview, you do not think about it. You just write it.