Maximum Number of Groups Getting Fresh Donuts

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 themaximum possible number of happy groups after rearranging the groups.

Examples

Example 1

1
2
3
4
5
6
7



    
    
    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

1
2
3
4
5
6

    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

Method 1 – Bitmask DP (Memoization)

Intuition

The key is to maximize the number of groups that start with a fresh batch (i.e., the sum of previous leftovers is 0 modulo batchSize). Since the number of groups is small (≤ 30), we can use bitmask DP to try all possible group orderings, tracking the current remainder and the count of each remainder.

Approach

Count the number of groups that are already happy (group size % batchSize == 0).
For the rest, count how many groups have each possible remainder (1 to batchSize-1).
Use memoization (DP) with the current state (tuple of counts for each remainder) and the current remainder.
For each possible next group (with nonzero count), try to serve it, update the state, and recurse.
If the current remainder is 0, increment the happy group count.
Return the maximum number of happy groups.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
public:
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        vector<int> cnt(batchSize);
        int ans = 0;
        for (int g : groups) {
            if (g % batchSize == 0) ans++;
            else cnt[g % batchSize]++;
        }
        unordered_map<string, int> memo;
        function<int(int, vector<int>&)> dfs = [&](int rem, vector<int>& c) {
            string key = to_string(rem) + ",";
            for (int x : c) key += to_string(x) + ",";
            if (memo.count(key)) return memo[key];
            int res = 0;
            for (int i = 1; i < batchSize; ++i) {
                if (c[i]) {
                    c[i]--;
                    int add = (rem == 0 ? 1 : 0);
                    res = max(res, dfs((rem + i) % batchSize, c) + add);
                    c[i]++;
                }
            }
            return memo[key] = res;
        };
        ans += dfs(0, cnt);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


import "strconv"
func maxHappyGroups(batchSize int, groups []int) int {
    cnt := make([]int, batchSize)
    ans := 0
    for _, g := range groups {
        if g%batchSize == 0 {
            ans++
        } else {
            cnt[g%batchSize]++
        }
    }
    memo := map[string]int{}
    var dfs func(int, []int) int
    dfs = func(rem int, c []int) int {
        key := strconv.Itoa(rem) + ","
        for _, x := range c {
            key += strconv.Itoa(x) + ","
        }
        if v, ok := memo[key]; ok {
            return v
        }
        res := 0
        for i := 1; i < batchSize; i++ {
            if c[i] > 0 {
                c[i]--
                add := 0
                if rem == 0 {
                    add = 1
                }
                tmp := dfs((rem+i)%batchSize, c) + add
                if tmp > res {
                    res = tmp
                }
                c[i]++
            }
        }
        memo[key] = res
        return res
    }
    ans += dfs(0, cnt)
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


import java.util.*;
class Solution {
    public int maxHappyGroups(int batchSize, int[] groups) {
        int[] cnt = new int[batchSize];
        int ans = 0;
        for (int g : groups) {
            if (g % batchSize == 0) ans++;
            else cnt[g % batchSize]++;
        }
        Map<String, Integer> memo = new HashMap<>();
        return ans + dfs(0, cnt, batchSize, memo);
    }
    private int dfs(int rem, int[] c, int batchSize, Map<String, Integer> memo) {
        StringBuilder sb = new StringBuilder();
        sb.append(rem).append(",");
        for (int x : c) sb.append(x).append(",");
        String key = sb.toString();
        if (memo.containsKey(key)) return memo.get(key);
        int res = 0;
        for (int i = 1; i < batchSize; i++) {
            if (c[i] > 0) {
                c[i]--;
                int add = rem == 0 ? 1 : 0;
                res = Math.max(res, dfs((rem + i) % batchSize, c, batchSize, memo) + add);
                c[i]++;
            }
        }
        memo.put(key, res);
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
    fun maxHappyGroups(batchSize: Int, groups: IntArray): Int {
        val cnt = IntArray(batchSize)
        var ans = 0
        for (g in groups) {
            if (g % batchSize == 0) ans++
            else cnt[g % batchSize]++
        }
        val memo = mutableMapOf<String, Int>()
        fun dfs(rem: Int, c: IntArray): Int {
            val key = buildString {
                append(rem).append(",")
                c.forEach { append(it).append(",") }
            }
            memo[key]?.let { return it }
            var res = 0
            for (i in 1 until batchSize) {
                if (c[i] > 0) {
                    c[i]--
                    val add = if (rem == 0) 1 else 0
                    res = maxOf(res, dfs((rem + i) % batchSize, c) + add)
                    c[i]++
                }
            }
            memo[key] = res
            return res
        }
        return ans + dfs(0, cnt)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


from functools import cache
class Solution:
    def maxHappyGroups(self, batchSize: int, groups: list[int]) -> int:
        from collections import Counter
        cnt = [0] * batchSize
        ans = 0
        for g in groups:
            if g % batchSize == 0:
                ans += 1
            else:
                cnt[g % batchSize] += 1
        @cache
        def dfs(rem: int, c: tuple[int, ...]) -> int:
            res = 0
            for i in range(1, batchSize):
                if c[i]:
                    nc = list(c)
                    nc[i] -= 1
                    add = 1 if rem == 0 else 0
                    res = max(res, dfs((rem + i) % batchSize, tuple(nc)) + add)
            return res
        ans += dfs(0, tuple(cnt))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


use std::collections::HashMap;
impl Solution {
    pub fn max_happy_groups(batch_size: i32, groups: Vec<i32>) -> i32 {
        let mut cnt = vec![0; batch_size as usize];
        let mut ans = 0;
        for &g in &groups {
            if g % batch_size == 0 {
                ans += 1;
            } else {
                cnt[(g % batch_size) as usize] += 1;
            }
        }
        let mut memo = HashMap::new();
        fn dfs(rem: i32, c: &mut [i32], batch_size: i32, memo: &mut HashMap<Vec<i32>, i32>) -> i32 {
            let mut key = vec![rem];
            key.extend_from_slice(c);
            if let Some(&v) = memo.get(&key) { return v; }
            let mut res = 0;
            for i in 1..batch_size as usize {
                if c[i] > 0 {
                    c[i] -= 1;
                    let add = if rem == 0 { 1 } else { 0 };
                    res = res.max(dfs((rem + i as i32) % batch_size, c, batch_size, memo) + add);
                    c[i] += 1;
                }
            }
            memo.insert(key, res);
            res
        }
        ans + dfs(0, &mut cnt, batch_size, &mut memo)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    maxHappyGroups(batchSize: number, groups: number[]): number {
        const cnt = Array(batchSize).fill(0);
        let ans = 0;
        for (const g of groups) {
            if (g % batchSize === 0) ans++;
            else cnt[g % batchSize]++;
        }
        const memo = new Map<string, number>();
        function dfs(rem: number, c: number[]): number {
            const key = rem + ',' + c.join(',');
            if (memo.has(key)) return memo.get(key)!;
            let res = 0;
            for (let i = 1; i < batchSize; i++) {
                if (c[i]) {
                    c[i]--;
                    const add = rem === 0 ? 1 : 0;
                    res = Math.max(res, dfs((rem + i) % batchSize, c) + add);
                    c[i]++;
                }
            }
            memo.set(key, res);
            return res;
        }
        return ans + dfs(0, cnt);
    }
}

Complexity

⏰ Time complexity: O(batchSize * (groups.length)^{batchSize}) in the worst case, but practical due to memoization and small batchSize (≤ 9).
🧺 Space complexity: O((groups.length)^{batchSize}) for the memoization table.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Bitmask DP (Memoization)#

Intuition#

Approach#

Code#

Complexity#