#1815

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Number of Groups Getting Fresh Donuts

Reorder groups to maximize happy customers by using state transition dynamic programming with bitmasking for optimal batch allocation.

array dynamic programming bit manipulation memoization bitmask

Problem Statement

A donut shop bakes donuts in fixed-size batches. Each group of customers must receive all their donuts consecutively, and a group is happy only if the first customer receives a fresh donut. You are given an integer batchSize and an array groups where groups[i] represents the size of the i-th group.

You may rearrange the order of groups to maximize happiness. Return the maximum number of happy groups achievable. Each customer receives exactly one donut, and leftover donuts from previous batches may affect subsequent groups' happiness.

Examples

Example 1

Input: batchSize = 3, groups = [1,2,3,4,5,6]

Output: 4

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

Example details omitted.

Constraints

1 <= batchSize <= 9
1 <= groups.length <= 30
1 <= groups[i] <= 109

Solution Approach

Modulo Preprocessing

Convert each group size to its remainder modulo batchSize. Groups with remainder zero are immediately happy. Count the occurrences of each remainder to form the initial state for dynamic programming.

State Transition with Bitmask

Use a bitmask or tuple to represent the remaining groups for each remainder. Recursively explore each possible next group, updating the current sum modulo batchSize, and memoize results to avoid recalculating identical states.

Maximizing Happy Groups

At each recursive step, if the current sum modulo batchSize is zero, the next chosen group will be happy. Track the maximum number of happy groups achievable from each state and return the global maximum.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is roughly O(batchSize^groups.length) due to all possible state combinations, reduced with memoization and pruning. Space complexity is O(batchSize^groups.length) for memoization storage.

What Interviewers Usually Probe

Noticing that direct permutation is infeasible due to group length.
Observing that happy groups depend on sum modulo batchSize.
Asking for dynamic programming optimization using remainders.

Common Pitfalls or Variants

Common pitfalls

Forgetting that only the first customer in a batch affects happiness.
Neglecting groups that are multiples of batchSize which are immediately happy.
Failing to memoize states leading to TLE on larger inputs.

Follow-up variants

Maximize happy groups with variable batch sizes per day.
Compute minimum leftover donuts while maximizing happy groups.
Adapt the solution to include group-specific donut preferences affecting happiness.

FAQ

What pattern does Maximum Number of Groups Getting Fresh Donuts use?

It uses state transition dynamic programming with bitmasking to manage group remainders modulo batchSize efficiently.

Can we brute-force all group orderings?

Brute force is infeasible due to factorial growth; dynamic programming with memoization is required for optimal performance.

How do groups with size multiple of batchSize affect happiness?

They are automatically happy since their first customer always receives a fresh donut without leftovers.

Is memoization necessary for this problem?

Yes, memoization prevents recalculating identical remainder states and avoids time limit exceeded errors.

How does modulo preprocessing simplify the solution?

It reduces the problem to tracking remainders, allowing state transitions to focus on batch fills rather than full group permutations.

terminal

Solution

Solution 1: 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:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        @cache
        def dfs(state, mod):
            res = 0
            x = int(mod == 0)
            for i in range(1, batchSize):
                if state >> (i * 5) & 31:
                    t = dfs(state - (1 << (i * 5)), (mod + i) % batchSize)
                    res = max(res, t + x)
            return res

        state = ans = 0
        for v in groups:
            i = v % batchSize
            ans += i == 0
            if i:
                state += 1 << (i * 5)
        ans += dfs(state, 0)
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        @cache
        def dfs(state, mod):
            res = 0
            x = int(mod == 0)
            for i in range(1, batchSize):
                if state >> (i * 5) & 31:
                    t = dfs(state - (1 << (i * 5)), (mod + i) % batchSize)
                    res = max(res, t + x)
            return res

        state = ans = 0
        for v in groups:
            i = v % batchSize
            ans += i == 0
            if i:
                state += 1 << (i * 5)
        ans += dfs(state, 0)
        return ans

Continue Practicing

#1799 maximize score after n operations #1755 closest subsequence sum #1879 minimum xor sum of two arrays