Leetcode 1815. Maximum Number of Groups Getting Fresh Donuts Solution
Problem Explanation
There is a donut shop that makes donuts in batches. Each batch has a certain quantity, called batchSize. The shop must finish serving all the donuts of a batch before serving donuts from the next batch. We 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 receive 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, meaning the first customer of the group does not receive a donut that was left over from the previous group.
We need to find the maximum possible number of happy groups after rearranging the groups.
Approach
For solving this problem, we can use a combination of a greedy approach (to solve simpler parts of the problem) and dynamic programming (to solve more complex parts):
- First, count the frequency of each group modulo
batchSize. For example, ifbatchSize = 4andgroups = [1,3,2,5,2,2,1,6], we would get the following frequencies:[0, 3, 3, 1]. - For each group
g, if its size modulobatchSizeis0, we can count it as a happy group immediately, as it doesn't affect the freshness of the next group. - For each non-zero modulo
g, if there is a group that can be paired withgto form a total ofbatchSizedonuts (i.e., there exists another grouphwithg + h = batchSize), we can make both groups happy by rearranging them. This is a greedy approach, as pairing these groups optimally can maximize our happy groups count. - For the remaining groups, we can find the optimal arrangement by recursively calculating the maximum happy groups for each partition and keeping track of the current remainder.
- The final result is the sum of the happy groups found in steps 2 to 4.
Solution
C++
1#include <vector>
2#include <map>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7 public:
8 int maxHappyGroups(int batchSize, vector<int>& groups) {
9 int happy = 0;
10 vector<int> freq(batchSize);
11
12 // Calculate frequencies and count happy groups with modulo 0
13 for (int g : groups) {
14 g %= batchSize;
15 if (g == 0) {
16 ++happy;
17 } else if (freq[batchSize - g]) {
18 --freq[batchSize - g];
19 ++happy;
20 } else {
21 ++freq[g];
22 }
23 }
24
25 // Find the optimal arrangement by recursively calculating maximum happy groups
26 return happy + dp(freq, 0, batchSize);
27 }
28
29 private:
30 map<vector<int>, int> memo;
31
32 int dp(const vector<int>& freq, int r, const int& batchSize) {
33
34 // If we have memoized the result for this frequency vector, return it
35 if (const auto it = memo.find(freq); it != cend(memo))
36 return it->second;
37
38 int ans = 0;
39
40 // Check if we have any remaining non-zero frequency groups
41 if (any_of(begin(freq), end(freq), [](int f) { return f != 0; })) {
42 for (int i = 0; i < freq.size(); ++i)
43 if (freq[i]) {
44 vector<int> newFreq(freq);
45 --newFreq[i]; // Decrease the frequency by 1
46 ans = max(ans, dp(newFreq, (r + i) % batchSize, batchSize));
47 }
48 // If the current remainder "r" is 0, we can increase the answer by 1
49 if (r == 0)
50 ++ans;
51 }
52
53 // Save the calculated result in memo map and return it
54 return memo[freq] = ans;
55 }
56};
Example Walkthrough
Let's consider the provided example:
1Input: batchSize = 3, groups = [1,2,3,4,5,6] 2Output: 4
- Calculate the frequency of each group modulo
batchSize:[1, 2, 3, 1, 2, 0]→[0, 3, 3] - Count happy groups with modulo 0: There is no group with size
3k, sohappy = 0. - Pair non-zero modulo groups: We can pair 3 groups of size
1with 3 groups of size2. - Find the optimal arrangement for remaining groups: In this case, all groups are already paired.
- The result is
happy (0) + paired groups (3) = 4.### Python
1from collections import defaultdict
2
3class Solution:
4 def maxHappyGroups(self, batchSize: int, groups: list[int]) -> int:
5 happy = 0
6 freq = [0] * batchSize
7
8 # Calculate frequencies and count happy groups with modulo 0
9 for g in groups:
10 g %= batchSize
11 if g == 0:
12 happy += 1
13 elif freq[batchSize - g]:
14 freq[batchSize - g] -= 1
15 happy += 1
16 else:
17 freq[g] += 1
18
19 memo = dict()
20
21 def dp(freq, r):
22 # If we have memoized the result for this frequency vector, return it
23 tup_freq = tuple(freq)
24 if tup_freq in memo:
25 return memo[tup_freq]
26
27 ans = 0
28
29 # Check if we have any remaining non-zero frequency groups
30 if any(f != 0 for f in freq):
31 for i in range(len(freq)):
32 if freq[i]:
33 new_freq = list(freq)
34 new_freq[i] -= 1 # Decrease the frequency by 1
35 ans = max(ans, dp(new_freq, (r + i) % batchSize))
36 # If the current remainder "r" is 0, we can increase the answer by 1
37 if r == 0:
38 ans += 1
39
40 # Save the calculated result in memo map and return it
41 memo[tup_freq] = ans
42 return ans
43
44 # Find the optimal arrangement by recursively calculating maximum happy groups
45 return happy + dp(freq, 0)
JavaScript
1class Solution {
2 maxHappyGroups(batchSize, groups) {
3 let happy = 0;
4 let freq = Array(batchSize).fill(0);
5
6 // Calculate frequencies and count happy groups with modulo 0
7 groups.forEach(g => {
8 g %= batchSize;
9 if (g === 0) {
10 happy++;
11 } else if (freq[batchSize - g]) {
12 freq[batchSize - g]--;
13 happy++;
14 } else {
15 freq[g]++;
16 }
17 });
18
19 let memo = new Map();
20
21 function dp(freq, r) {
22 // If we have memoized the result for this frequency vector, return it
23 const tup_freq = freq.toString();
24 if (memo.has(tup_freq)) {
25 return memo.get(tup_freq);
26 }
27
28 let ans = 0;
29
30 // Check if we have any remaining non-zero frequency groups
31 if (freq.some(f => f !== 0)) {
32 freq.forEach((f, i) => {
33 if (f) {
34 const new_freq = [...freq];
35 new_freq[i]--; // Decrease the frequency by 1
36 ans = Math.max(ans, dp(new_freq, (r + i) % batchSize));
37 }
38 });
39 // If the current remainder "r" is 0, we can increase the answer by 1
40 if (r === 0) {
41 ans++;
42 }
43 }
44
45 // Save the calculated result in memo map and return it
46 memo.set(tup_freq, ans);
47 return ans;
48 }
49
50 // Find the optimal arrangement by recursively calculating maximum happy groups
51 return happy + dp(freq, 0);
52 }
53}
Now you have a full solution in Python, JavaScript, and C++ that solves the problem of finding the maximum number of happy groups after rearranging the groups.