Maximum Number of Groups Getting Fresh Donuts

// Accepted solution for LeetCode #1815: Maximum Number of Groups Getting Fresh Donuts
class Solution {
    private Map<Long, Integer> f = new HashMap<>();
    private int size;

    public int maxHappyGroups(int batchSize, int[] groups) {
        size = batchSize;
        int ans = 0;
        long state = 0;
        for (int g : groups) {
            int i = g % size;
            if (i == 0) {
                ++ans;
            } else {
                state += 1l << (i * 5);
            }
        }
        ans += dfs(state, 0);
        return ans;
    }

    private int dfs(long state, int mod) {
        if (f.containsKey(state)) {
            return f.get(state);
        }
        int res = 0;
        for (int i = 1; i < size; ++i) {
            if ((state >> (i * 5) & 31) != 0) {
                int t = dfs(state - (1l << (i * 5)), (mod + i) % size);
                res = Math.max(res, t + (mod == 0 ? 1 : 0));
            }
        }
        f.put(state, res);
        return res;
    }
}

// Accepted solution for LeetCode #1815: Maximum Number of Groups Getting Fresh Donuts
func maxHappyGroups(batchSize int, groups []int) (ans int) {
	state := 0
	for _, v := range groups {
		i := v % batchSize
		if i == 0 {
			ans++
		} else {
			state += 1 << (i * 5)
		}
	}
	f := map[int]int{}
	var dfs func(int, int) int
	dfs = func(state, mod int) int {
		if v, ok := f[state]; ok {
			return v
		}
		res := 0
		x := 0
		if mod == 0 {
			x = 1
		}
		for i := 1; i < batchSize; i++ {
			if state>>(i*5)&31 != 0 {
				t := dfs(state-1<<(i*5), (mod+i)%batchSize)
				res = max(res, t+x)
			}
		}
		f[state] = res
		return res
	}
	ans += dfs(state, 0)
	return
}

# Accepted solution for LeetCode #1815: Maximum Number of Groups Getting Fresh Donuts
class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        @cache
        def dfs(state, mod):
            res = 0
            x = int(mod == 0)
            for i in range(1, batchSize):
                if state >> (i * 5) & 31:
                    t = dfs(state - (1 << (i * 5)), (mod + i) % batchSize)
                    res = max(res, t + x)
            return res

        state = ans = 0
        for v in groups:
            i = v % batchSize
            ans += i == 0
            if i:
                state += 1 << (i * 5)
        ans += dfs(state, 0)
        return ans

// Accepted solution for LeetCode #1815: Maximum Number of Groups Getting Fresh Donuts
/**
 * [1815] 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 1^st, 2^nd, 4^th, and 6^th 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
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts/
// discuss: https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn max_happy_groups(batch_size: i32, groups: Vec<i32>) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_1815_example_1() {
        let batch_size = 3;
        let groups = vec![1, 2, 3, 4, 5, 6];

        let result = 4;

        assert_eq!(Solution::max_happy_groups(batch_size, groups), result);
    }

    #[test]
    #[ignore]
    fn test_1815_example_2() {
        let batch_size = 4;
        let groups = vec![1, 3, 2, 5, 2, 2, 1, 6];

        let result = 4;

        assert_eq!(Solution::max_happy_groups(batch_size, groups), result);
    }
}

// Accepted solution for LeetCode #1815: Maximum Number of Groups Getting Fresh Donuts
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1815: Maximum Number of Groups Getting Fresh Donuts
// class Solution {
//     private Map<Long, Integer> f = new HashMap<>();
//     private int size;
// 
//     public int maxHappyGroups(int batchSize, int[] groups) {
//         size = batchSize;
//         int ans = 0;
//         long state = 0;
//         for (int g : groups) {
//             int i = g % size;
//             if (i == 0) {
//                 ++ans;
//             } else {
//                 state += 1l << (i * 5);
//             }
//         }
//         ans += dfs(state, 0);
//         return ans;
//     }
// 
//     private int dfs(long state, int mod) {
//         if (f.containsKey(state)) {
//             return f.get(state);
//         }
//         int res = 0;
//         for (int i = 1; i < size; ++i) {
//             if ((state >> (i * 5) & 31) != 0) {
//                 int t = dfs(state - (1l << (i * 5)), (mod + i) % size);
//                 res = Math.max(res, t + (mod == 0 ? 1 : 0));
//             }
//         }
//         f.put(state, res);
//         return res;
//     }
// }