1815. 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 **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

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> memo = new HashMap<>();

  private int dp(int[] freq, int r, int batchSize) {
    final String hashed = hash(freq);
    if (memo.containsKey(hashed))
      return memo.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, (r + i) % batchSize, batchSize));
        }
      if (r == 0)
        ++ans;
    }

    memo.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();
  }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).