# Maximum Number of Groups Getting Fresh Donuts
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-groups-getting-fresh-donuts
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## 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 <= 9`
* `1 <= groups.length <= 30`
* `1 <= groups[i] <= 109`

# Approaches
## Backtracking with Memoization
This approach uses recursion to explore all valid orderings of groups. To make this feasible, we don't explore permutations of individual groups but rather permutations of group *types*, where a type is defined by the group size's remainder modulo `batchSize`. We use memoization (a form of dynamic programming) to store and reuse results for subproblems, avoiding redundant computations.
**Time:** O(C(N + B - 1, B - 1) * B^2), where N is the number of groups with non-zero remainders (<= 30) and B is `batchSize`. For each state, we iterate through B possible choices. · **Space:** O(C(N + B - 1, B - 1) * B), where N is the number of groups with non-zero remainders (<= 30) and B is `batchSize`. This is for the memoization table.
**Pros:** Guaranteed to find the optimal solution.; It's a general approach that correctly models the problem's state transitions.; Feasible for the given constraints on `batchSize` and `groups.length`.
**Cons:** The state space for the memoization can be large, leading to higher time and memory consumption compared to more optimized approaches.; Without further optimizations, this approach might be too slow if the constraints were slightly larger.
### Explanation
The core idea is to define a state by `(counts, leftovers)`, where `counts` is an array representing the number of available groups for each remainder, and `leftovers` is the number of donuts remaining from the previous batch. A recursive function explores the optimal path from any given state.

When `leftovers` is 0, any group we choose to serve next will be happy. This adds 1 to our count, and we transition to a new state with `leftovers` equal to that group's remainder. If `leftovers` is not 0, the next group is not happy, and we simply transition to a new state with updated `leftovers`. The function tries every possible next group and chooses the path that yields the maximum total happy groups.

To implement memoization, the state `(counts, leftovers)` can be converted into a unique key (e.g., a string) to use in a hash map.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    private int batchSize;
    private Map<String, Integer> memo;

    public int maxHappyGroups(int batchSize, int[] groups) {
        this.batchSize = batchSize;
        this.memo = new HashMap<>();
        
        int[] counts = new int[batchSize];
        for (int g : groups) {
            counts[g % batchSize]++;
        }
        
        int initialHappy = counts[0];
        counts[0] = 0; // These are handled separately and not part of the recursion.
        
        return initialHappy + solve(counts, 0);
    }

    private int solve(int[] counts, int leftovers) {
        StringBuilder keyBuilder = new StringBuilder();
        boolean allZero = true;
        for (int i = 1; i < batchSize; i++) {
            keyBuilder.append(counts[i]).append(",");
            if (counts[i] > 0) {
                allZero = false;
            }
        }

        if (allZero) {
            return 0;
        }

        keyBuilder.append(leftovers);
        String key = keyBuilder.toString();

        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int maxHappy = 0;
        int currentHappy = (leftovers == 0) ? 1 : 0;

        for (int i = 1; i < batchSize; i++) {
            if (counts[i] > 0) {
                counts[i]--;
                int result = solve(counts, (leftovers + i) % batchSize);
                maxHappy = Math.max(maxHappy, currentHappy + result);
                counts[i]++; // Backtrack
            }
        }
        
        memo.put(key, maxHappy);
        return maxHappy;
    }
}
```
### Algorithm
1.  First, we simplify the problem by focusing on the remainders of group sizes when divided by `batchSize`. We use a `counts` array to store the frequency of each remainder from `0` to `batchSize - 1`.
2.  Groups with a remainder of `0` are special. If served when there are no leftover donuts, they are happy and leave no leftovers for the next group. We can count all such groups as happy and handle them separately. The initial number of happy groups is `counts[0]`.
3.  The main challenge is to arrange the remaining groups (with remainders `1` to `batchSize - 1`) to maximize additional happy groups. This can be modeled as a state-space search problem, which we can solve using recursion with memoization (top-down dynamic programming).
4.  We define a recursive function, `solve(current_counts, leftovers)`, which calculates the maximum number of happy groups we can form given the `current_counts` of available groups and the current number of `leftovers` from the previous batch.
5.  The state for our recursion is defined by the tuple of counts `(counts[1], ..., counts[batchSize-1])` and the `leftovers` value.
6.  **Recursive Function `solve(counts, leftovers)`:**
    *   **Base Case:** If all counts for non-zero remainders are zero, no more groups can be served. Return 0.
    *   **Memoization:** Check if the result for the state `(counts, leftovers)` is already computed. If so, return the stored value.
    *   **Recursive Step:** Iterate through all possible remainders `r` from `1` to `batchSize - 1`.
        *   If `counts[r] > 0`, we can choose to serve a group with this remainder.
        *   The number of happy groups for this choice is `(leftovers == 0 ? 1 : 0)` for the current group, plus the result of the recursive call for the subsequent state: `solve(new_counts, (leftovers + r) % batchSize)`.
        *   We take the maximum value over all possible choices of `r`.
    *   Store the result in the memoization table and return it.
7.  The final answer is `counts[0]` plus the result of the initial call `solve(initial_counts, 0)`.

## Optimized DP with Greedy Pre-computation
This approach significantly optimizes the previous one by first applying a greedy strategy. We identify and process pairs of groups that complement each other (i.e., their remainders sum to `batchSize`). This is an optimal greedy choice because each such pair can be arranged to contribute one happy group and return the system to a `leftovers = 0` state, without negatively impacting the arrangements of other groups. By handling these pairs first, we drastically reduce the number of groups and the complexity of the state space for the subsequent dynamic programming step, leading to a much faster solution.
**Time:** O(B + C(N' + B' - 1, B' - 1) * B^2), where N' and B' are the number of remaining groups and remainder types. The practical performance is excellent for the given constraints. · **Space:** O(C(N' + B' - 1, B' - 1) * B), where N' and B' are the (much smaller) number of remaining groups and remainder types after greedy pairing.
**Pros:** Much more efficient in practice due to the significantly reduced state space for the DP part.; The greedy pre-computation is simple and provably optimal.; Combines the strength of a greedy algorithm with the correctness of dynamic programming.
**Cons:** The implementation is slightly more complex due to the initial greedy pairing logic.
### Explanation
The algorithm first preprocesses the groups by counting remainders. It adds `counts[0]` to the result. Then, it greedily pairs groups with remainders `i` and `batchSize - i`. For each pair, we increment the happy group count. This is because we can schedule these pairs as `[i, batchSize-i]`. If we start with 0 leftovers, group `i` is happy, and after serving group `batchSize-i`, the leftovers are `(0 + i + batchSize - i) % batchSize = 0`. So we get one happy group and return to the 0-leftover state. After exhausting all such pairs, we are left with a smaller problem, which we solve using the same DP approach as before.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    private int batchSize;
    private Map<String, Integer> memo;

    public int maxHappyGroups(int batchSize, int[] groups) {
        this.batchSize = batchSize;
        this.memo = new HashMap<>();
        
        int[] counts = new int[batchSize];
        for (int g : groups) {
            counts[g % batchSize]++;
        }
        
        int happyGroups = counts[0];
        counts[0] = 0;

        // Greedy pairing
        for (int i = 1; i <= batchSize / 2; i++) {
            if (i * 2 == batchSize) {
                happyGroups += counts[i] / 2;
                counts[i] %= 2;
            } else {
                int pairs = Math.min(counts[i], counts[batchSize - i]);
                happyGroups += pairs;
                counts[i] -= pairs;
                counts[batchSize - i] -= pairs;
            }
        }
        
        return happyGroups + solve(counts, 0);
    }

    private int solve(int[] counts, int leftovers) {
        StringBuilder keyBuilder = new StringBuilder();
        boolean allZero = true;
        for (int i = 1; i < batchSize; i++) {
            keyBuilder.append(counts[i]).append(",");
            if (counts[i] > 0) {
                allZero = false;
            }
        }

        if (allZero) {
            return 0;
        }

        keyBuilder.append(leftovers);
        String key = keyBuilder.toString();

        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int maxHappy = 0;
        int currentHappy = (leftovers == 0) ? 1 : 0;

        for (int i = 1; i < batchSize; i++) {
            if (counts[i] > 0) {
                counts[i]--;
                int result = solve(counts, (leftovers + i) % batchSize);
                maxHappy = Math.max(maxHappy, currentHappy + result);
                counts[i]++; // Backtrack
            }
        }
        
        memo.put(key, maxHappy);
        return maxHappy;
    }
}
```
### Algorithm
1.  Calculate the frequency of remainders `counts[r]` for `r` from `0` to `batchSize - 1`.
2.  Initialize `happy_groups = counts[0]`. These groups are handled first as they don't affect the leftover state for other groups.
3.  **Greedy Pairing Strategy:**
    *   For each remainder `r` from `1` to `(batchSize - 1) / 2`, we can pair a group of remainder `r` with a group of remainder `batchSize - r`. When served together, their total size is a multiple of `batchSize`, effectively resetting the leftovers to what it was before serving the pair. This sequence `(r, batchSize-r)` when starting with `leftovers=0` yields one happy group (`r`) and returns the state to `leftovers=0`. This is always a beneficial move.
    *   The number of such pairs is `p = min(counts[r], counts[batchSize - r])`. Add `p` to `happy_groups`.
    *   Update the counts: `counts[r] -= p`, `counts[batchSize - r] -= p`.
4.  **Handle Middle Element:** If `batchSize` is even, the remainder `r = batchSize / 2` is its own complement. Two such groups also sum to `batchSize`. We can form `p = counts[batchSize / 2] / 2` pairs. Add `p` to `happy_groups` and update `counts[batchSize / 2] %= 2`.
5.  After these greedy steps, we are left with a much smaller set of groups.
6.  Apply the same backtracking with memoization approach (`solve(counts, leftovers)`) as in the previous method to this reduced problem. The initial call will be `solve(remaining_counts, 0)`.
7.  The final answer is the sum of `happy_groups` from the greedy part and the result from the recursive part.

# Solutions
### Java

```java
class Solution { private Map < Long , Integer > f = new HashMap <>(); private int size ; public int maxHappyGroups ( int batchSize , int [] groups ) { size = batchSize ; int ans = 0 ; long state = 0 ; for ( int g : groups ) { int i = g % size ; if ( i == 0 ) { ++ ans ; } else { state += 1 l << ( i * 5 ); } } ans += dfs ( state , 0 ); return ans ; } private int dfs ( long state , int mod ) { if ( f . containsKey ( state )) { return f . get ( state ); } int res = 0 ; for ( int i = 1 ; i < size ; ++ i ) { if (( state >> ( i * 5 ) & 31 ) != 0 ) { int t = dfs ( state - ( 1 l << ( i * 5 )), ( mod + i ) % size ); res = Math . max ( res , t + ( mod == 0 ? 1 : 0 )); } } f . put ( state , res ); return res ; } }
```

### CPP

```cpp
class Solution { public: int maxHappyGroups ( int batchSize , vector < int >& groups ) { using ll = long long ; unordered_map < ll , int > f ; ll state = 0 ; int ans = 0 ; for ( auto & v : groups ) { int i = v % batchSize ; ans += i == 0 ; if ( i ) { state += 1ll << ( i * 5 ); } } function < int ( ll , int ) > dfs = [ & ]( ll state , int mod ) { if ( f . count ( state )) { return f [ state ]; } int res = 0 ; int x = mod == 0 ; for ( int i = 1 ; i < batchSize ; ++ i ) { if ( state >> ( i * 5 ) & 31 ) { int t = dfs ( state - ( 1ll << ( i * 5 )), ( mod + i ) % batchSize ); res = max ( res , t + x ); } } return f [ state ] = res ; }; ans += dfs ( state , 0 ); return ans ; } };
```

### Python

```python
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
```