LeetCode 1815: Maximum Number of Groups Getting Fresh Donuts

Explanation:

To maximize the number of happy groups, we need to find the maximum number of groups that can be served without any leftovers from the previous group. We can achieve this by using a dynamic programming approach. We will iterate through all possible combinations of groups and for each combination, we will check if it can form a happy group. To optimize the process, we can use a bitmask to represent the state of each group.

1. Create a memoization table to store the maximum number of happy groups for a given bitmask state.
2. Iterate through all possible bitmask states and for each state:
   • Iterate through all groups and check if the current group can be added to the current state without any leftovers from previous groups.
   • Update the memoization table with the maximum number of happy groups for the current state.
3. Return the maximum number of happy groups from the memoization table for the full bitmask state.

Time Complexity: O(2^n * n), where n is the number of groups. Space Complexity: O(2^n)

:

class Solution {
    public int maxHappyGroups(int batchSize, int[] groups) {
        int n = groups.length;
        int[] count = new int[batchSize];
        int res = 0;

        for (int group : groups) {
            count[group % batchSize]++;
            if (group % batchSize == 0) {
                res++;
            }
        }

        int[] dp = new int[1 << batchSize];
        for (int mask = 1; mask < 1 << batchSize; mask++) {
            for (int i = 0; i < batchSize; i++) {
                if (count[i] == 0) {
                    continue;
                }
                int newMask = (mask + batchSize - i) % batchSize;
                dp[mask] = Math.max(dp[mask], dp[mask ^ (1 << i)] + (newMask == 0 ? 1 : 0));
            }
        }

        return res + dp[(1 << batchSize) - 1];
    }
}