We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Groups Getting Fresh Donuts

Number: 1924

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

We are given a donut shop that bakes donuts in batches of a fixed size (batchSize). Each arriving group of customers must be served in its entirety before moving to the next group and is happy only when the first customer in the group receives a freshly baked donut (i.e. not a leftover from a previous group). Given the sizes of the groups, we can rearrange their order arbitrarily. The goal is to maximize the number of happy groups after serving all groups in some order.

Key Insights

  • Groups whose sizes are perfectly divisible by batchSize (remainder 0) are immediately happy.
  • For the remaining groups, compute each group’s remainder when divided by batchSize.
  • Use dynamic programming (DP) with memoization to explore the different orders in which groups (characterized by their remainders) can be served.
  • The DP state tracks the counts of groups for each remainder and the current leftover donuts from previous batches.
  • When a group's remainder added to the leftover becomes 0 modulo batchSize, that group will be happy.
  • Because batchSize is small (up to 9) and groups length is at most 30, the combinatorial state can be efficiently cached.

Space and Time Complexity

Time Complexity: O(state_size * batchSize) where state_size depends on the counts of remainder groups. In worst-case the exploration is exponential in small numbers, which is viable given the constraints. Space Complexity: O(state_size) due to memoization caching intermediate DP state results.

Solution

We start by counting groups with no remainder (i.e. groups that directly make a fresh batch) and then reduce other groups into their modulo remainder counts. We then define a recursive DP (DFS) method that, given the current state (the frequency of each remainder and the leftover donuts), tries all possible decisions:

  1. Pick a group (denoted by its remainder) that remains in the state.
  2. Update the leftover donuts as (current leftover + r) mod batchSize.
  3. If the current leftover was 0, then the group being served gets a fresh batch, which counts as an additional happy group.
  4. Recursively solve for the new state and choose the transition that maximizes the overall number of happy groups. Memoization is used to cache the outcomes for a given state, identified by the counts and current leftover, thereby avoiding redundant computations.

Code Solutions

# Python solution using recursion and memoization

from functools import lru_cache
from collections import Counter

def maxHappyGroups(batchSize, groups):
    # Count groups that fit perfectly into a batch.
    immediate_happy = 0
    remainder_counts = [0] * batchSize
    for group in groups:
        remainder = group % batchSize
        if remainder == 0:
            immediate_happy += 1
        else:
            remainder_counts[remainder] += 1

    # DFS with memoization. The state is represented as a tuple of counts and the current leftover donuts.
    @lru_cache(maxsize=None)
    def dfs(state, leftover):
        max_happy = 0
        state = list(state)
        # Try every remainder possibility (ignoring r=0 as those are pre-counted)
        for r in range(1, batchSize):
            if state[r] > 0:
                state[r] -= 1
                new_leftover = (leftover + r) % batchSize
                # If there is no leftover from the previous step, this group gets fresh donuts.
                happy_extra = 1 if leftover == 0 else 0
                max_happy = max(max_happy, dfs(tuple(state), new_leftover) + happy_extra)
                state[r] += 1
        return max_happy

    result = immediate_happy + dfs(tuple(remainder_counts), 0)
    return result

# Example usage:
print(maxHappyGroups(3, [1,2,3,4,5,6]))  # Expected output: 4
← Back to All Questions