Formatted question description: https://leetcode.ca/all/1815.html

# 1815. Maximum Number of Groups Getting Fresh Donuts

## Level

Hard

## Description

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] <= 10^9`

## Solution

The aim of this problem is to find a permutation of `groups`

such that the number of prefix sums of `groups`

that can be divisible by `batchSize`

is the most. Use dynamic programming with compressed states to solve this.

```
class Solution {
public int maxHappyGroups(int batchSize, int[] groups) {
long state = 0;
int mod0 = 0;
for (int group : groups) {
group %= batchSize;
if (group == 0)
mod0++;
else
state += 1L << (group * 5);
}
Map<Long, Integer> map = new HashMap<Long, Integer>();
return mod0 + dp(0, state, batchSize, map);
}
public int dp(int curr, long state, int batchSize, Map<Long, Integer> map) {
if (!map.containsKey(state)) {
if (state == 0)
map.put(state, 0);
else {
int val = 0;
for (int i = 1; i < batchSize; i++) {
if ((state >>> (i * 5)) % 32 != 0) {
int nextVal = dp((curr + i) % batchSize, state - (1L << (i * 5)), batchSize, map);
val = Math.max(val, curr != 0 ? nextVal : nextVal + 1);
}
}
map.put(state, val);
}
}
return map.get(state);
}
}
```