Maximum Number of Groups Getting Fresh Donuts — LeetCode 1815 Python Solution

The 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.

Example

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.

Python solution

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

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems