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):

  1. First, count the frequency of each group modulo batchSize. For example, if batchSize = 4 and groups = [1,3,2,5,2,2,1,6], we would get the following frequencies: [0, 3, 3, 1].
  2. For each group g, if its size modulo batchSize is 0, we can count it as a happy group immediately, as it doesn't affect the freshness of the next group.
  3. For each non-zero modulo g, if there is a group that can be paired with g to form a total of batchSize donuts (i.e., there exists another group h with g + 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.
  4. 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.
  5. 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
  1. Calculate the frequency of each group modulo batchSize: [1, 2, 3, 1, 2, 0][0, 3, 3]
  2. Count happy groups with modulo 0: There is no group with size 3k, so happy = 0.
  3. Pair non-zero modulo groups: We can pair 3 groups of size 1 with 3 groups of size 2.
  4. Find the optimal arrangement for remaining groups: In this case, all groups are already paired.
  5. 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.