5707. Maximum Number of Groups Getting Fresh Donuts (Leetcode)

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

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

Step I (Understanding):

• The problem tells us that if a group gets some donut from previous batch, then they won't be happy. Or otherwise if a batch is freshly prepared for them, the group will be happy.
• This implies that, all donuts from the previous batch should be emptied, so that the current group can be happy.
• So now we can see that, the amount of donuts used when modded (taken remainder) with batchSize should be 0, inorder for the current group to be happy.

Step II (Thinking through):

• One thing we should see is that the order of groups really matters while serving, so that a particular group can be happy.
• For eg: if we have batchSize of 4 and groups as [3, 4, 1, 2], then if we order groups as [4, 3, 1, 2] it will give us result as 3. On the other hand if we take the order as [1, 2, 3, 4], the result will be 1.
• This is because when we use 4 first, the donut in that batch gets used up. Then when 3 and 1 are used, the second batch gets used up and so our answer becomes 3.
• The main aim here is to cluster the groups so that they would leave no donuts after their consumption, but we do not know how to order them.
• Try this eg for understanding the fact stated above (order matters and we don't know how to order): batchSize: 5 and [5, 4, 3, 1, 1, 1, 3].
• So we have to try all possible combinations, inorder to see which one gives the maximum results. So we will use recursion here.

Step III (Making provision for recursion):

• We can see that we have to bring the remainder to 0, so we will take the mod of all elements with batchSize (i.e element % batchSize).
• By doing this we will cluster all elements by their mod values.
• Now we will use them one by one, and check whether they for mod value of zero. If yes this will contribute 1 to the answer or else it will contribute 0 to the answer.

Step IV (Forming recursive solution):

• Let's do recursion by considering any mod value and reduce that mod value from array by 1.
• And will continue recursively this way, until every element from the array is exhausted.
• This is shown in the code below. But this will give TLE, since every states are computed multiple times.

int recur(int mod, int[] a) { boolean over = true; // checking if all groups have been served. for(int i = 1; i < a.length; i++) { if(a[i] != 0) { over = false; break; } } if(over) { return 0; } else { // if we had mod of 0 in this state // then we can see that, this is happy group // because it is being served fresh donut batch int cur = (mod == 0) ? 1 : 0; int max = 0; for(int i = 1; i < a.length; i++) { if(a[i] > 0) { a[i]--; // reducing 1 because 1 group is served currently // adding i to mod value, since ith group is taken max = Math.max(max, recur((mod + i) % a.length, a)); a[i]++; // again incrementing, for recursion to be working } } return max + cur; } }

Step V (From TLE to Accepted - Using Dynamic Programming):

• Let's cache every state through which we are going currently.
• For recursion we used both mod and array.
• So we will cache it and the current result so that this subproblem may not be recomputed.

Full Code (Java): class Solution { HashMap<String, Integer> dp; public int maxHappyGroups(int batchSize, int[] groups) { int[] a = new int[batchSize]; for(int i : groups) { a[i % batchSize]++; } int happy = a[0]; a[0] = 0; dp = new HashMap<>(); int ans = recur(0, a); return ans + happy; } int recur(int mod, int[] a) { boolean over = true; for(int i = 1; i < a.length; i++) { if(a[i] != 0) { over = false; break; } } if(over) { return 0; } else { // forming a key for caching String key = Arrays.toString(a) + "," + mod; // if key exists (means this state exists) // the result will be returned without further computation if(dp.containsKey(key)) { return dp.get(key); } int cur = (mod == 0) ? 1 : 0; int max = 0; for(int i = 1; i < a.length; i++) { if(a[i] > 0) { a[i]--; max = Math.max(max, recur((mod + i) % a.length, a)); a[i]++; } } // storing the computed result inside our cache dp.put(key, max + cur); return max + cur; } } }