1815. Maximum Number of Groups Getting Fresh Donuts LeetCode Solution

In this guide, you will get 1815. Maximum Number of Groups Getting Fresh Donuts LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Groups Getting Fresh Donuts problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Number of Groups Getting Fresh Donuts solution in C++
4. Maximum Number of Groups Getting Fresh Donuts solution in Java
5. Maximum Number of Groups Getting Fresh Donuts solution in Python
6. Additional Resources

Problem Statement of Maximum Number of Groups Getting Fresh Donuts

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

Complexity Analysis

• Time Complexity:
• Space Complexity:

1815. Maximum Number of Groups Getting Fresh Donuts LeetCode Solution in C++

class Solution {
 public:
  int maxHappyGroups(int batchSize, vector<int>& groups) {
    int happy = 0;
    vector<int> freq(batchSize);

    for (int g : groups) {
      g %= batchSize;
      if (g == 0) {
        ++happy;
      } else if (freq[batchSize - g]) {
        --freq[batchSize - g];
        ++happy;
      } else {
        ++freq[g];
      }
    }

    return happy + dp(freq, 0, batchSize);
  }

 private:
  map<vector<int>, int> mem;

  // Returns the maximum number of partitions can be formed.
  int dp(const vector<int>& freq, int remainder, const int& batchSize) {
    if (const auto it = mem.find(freq); it != mem.cend())
      return it->second;

    int ans = 0;

    if (ranges::any_of(freq, [](int f) { return f != 0; })) {
      for (int i = 0; i < freq.size(); ++i)
        if (freq[i]) {
          vector<int> newFreq(freq);
          --newFreq[i];
          ans = max(ans, dp(newFreq, (remainder + i) % batchSize, batchSize));
        }
      if (remainder == 0)
        ++ans;
    }

    return mem[freq] = ans;
  }
};
/* code provided by PROGIEZ */

1815. Maximum Number of Groups Getting Fresh Donuts LeetCode Solution in Java

class Solution {
  public int maxHappyGroups(int batchSize, int[] groups) {
    int happy = 0;
    int[] freq = new int[batchSize];

    for (int g : groups) {
      g %= batchSize;
      if (g == 0) {
        ++happy;
      } else if (freq[batchSize - g] > 0) {
        --freq[batchSize - g];
        ++happy;
      } else {
        ++freq[g];
      }
    }

    return happy + dp(freq, 0, batchSize);
  }

  private Map<String, Integer> mem = new HashMap<>();

  // Returns the maximum number of partitions can be formed.
  private int dp(int[] freq, int remainder, int batchSize) {
    final String hashed = hash(freq);
    if (mem.containsKey(hashed))
      return mem.get(hashed);

    int ans = 0;

    if (Arrays.stream(freq).anyMatch(f -> f != 0)) {
      for (int i = 0; i < freq.length; ++i)
        if (freq[i] > 0) {
          int[] newFreq = freq.clone();
          --newFreq[i];
          ans = Math.max(ans, dp(newFreq, (remainder + i) % batchSize, batchSize));
        }
      if (remainder == 0)
        ++ans;
    }

    mem.put(hash(freq), ans);
    return ans;
  }

  private String hash(int[] freq) {
    StringBuilder sb = new StringBuilder();
    for (final int f : freq)
      sb.append("#").append(f);
    return sb.toString();
  }
}
// code provided by PROGIEZ

1815. Maximum Number of Groups Getting Fresh Donuts LeetCode Solution in Python

class Solution:
  def maxHappyGroups(self, batchSize: int, groups: list[int]) -> int:
    happy = 0
    freq = [0] * batchSize

    for g in groups:
      g %= batchSize
      if g == 0:
        happy += 1
      elif freq[batchSize - g]:
        freq[batchSize - g] -= 1
        happy += 1
      else:
        freq[g] += 1

    @functools.lru_cache(None)
    def dp(freq: int, remainder: int) -> int:
      """Returns the maximum number of partitions can be formed."""
      ans = 0
      if any(freq):
        for i, f in enumerate(freq):
          if f:
            ans = max(ans, dp(freq[:i] + (f - 1,) +
                              freq[i + 1:], (remainder + i) % batchSize))
        if remainder == 0:
          ans += 1
      return ans

    return happy + dp(tuple(freq), 0)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.