Problem statement

https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts/

Solution

Quite difficult problem, we need to read problem restriction carefully to suceed. We can notice, that B <= 9 and this is the main point we will use.

  1. Let us first understand, what our problem is about. We have bunch of nubmers and we need to make them in special order, such that as much groups are divisible by B. Notice, that what matters, is not element g in groups, but in fact g % B.
  2. Now, we have elements in groups be numbers from 0 to B-1. Notice, that if we have element 0, than this group is always happy, so no need to consider it: remove it and add 1 to final answer. Also, notice, that if we have two elements, which give B in total, if we put them one after another, we will make happy group as well.
  3. Let us call position how many of each reminders we have, for example for case [1, 2, 3, 3, 4, 5, 5, 5] and B = 4, we have [4,1,2], because we have 4 numbers with reminder 1, 1 number with reminder 2 and 2 numbers with reminder 3.
  4. It is time now to use dfs(position, last), where position is what we discussed earlier and last is last number in our sequence. Where we can go from this position: we try to decrease one of the elements of position by one and run function recursively: we add 1 (using U == 0), if we make one more group happy.
  5. In the end we just run our dfs from positions we created.

Complexity

We have at most O(K), where K = B//2 non-zero elements in group and sum of all elements in groups is restricted by n. So we have no more than (n/K)^K possible positions here, which given problem restriction is quite small, so total time complexity is O((n/K)^K*K), because we can have upto K transitions from one state to others. Space complexity is the same.

Code

class Solution:
    def maxHappyGroups(self, B, groups):
        ans = sum(g%B == 0 for g in groups)
        groups = [g for g in groups if g%B != 0]

        pos = [0]*(B-1)
        for g in groups: pos[g%B - 1] += 1

        for i in range(B-1):
            t = min(pos[i], pos[B-i-2]) if 2*i != B - 2 else pos[i]//2
            ans += t
            pos[i] -= t
            pos[B-i-2] -= t
            
        if sum(pos) == 0: return ans

        @lru_cache(None)
        def dfs(position, last):
            if sum(position) == 0: return 0

            ans = float("-inf")
            for i in range(B - 1):
                if position[i] > 0:
                    t = [j for j in position]
                    t[i] -= 1
                    U = (last - (i + 1)) % B
                    ans = max(ans, dfs(tuple(t), U) + (U == 0))
                      
            return ans

        return max(dfs(tuple(pos), i) for i in range(1, B)) + ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 1815