Maximum Number of Groups Getting Fresh Donuts

Maximum Number of Groups Getting Fresh Donuts - Problem

There is a donut 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.

Input & Output

Example 1 — Basic Case

$ Input: batchSize = 3, groups = [1,2,3,1,2]

› Output: 4

💡 Note: Optimal arrangement [3,1,2,1,2]: Group 3 (remainder 0) is happy, group 1 starts fresh (remainder was 0), group 2 starts fresh (remainder was 1), group 1 starts fresh (remainder was 0), group 2 is not fresh (remainder was 1). Total: 4 happy groups.

Example 2 — Small Batch

$ Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6]

› Output: 4

💡 Note: Groups with remainder 0 (like 4,8) are always happy. Groups with remainders that sum to batchSize can be paired strategically.

Example 3 — All Same Remainder

$ Input: batchSize = 2, groups = [1,1,1,1]

› Output: 2

💡 Note: All groups have remainder 1. First group is happy, second is not (remainder 1), third is happy (remainder 0 after second), fourth is not. Maximum: 2 happy groups.

Constraints

1 ≤ batchSize ≤ 9
1 ≤ groups.length ≤ 30
1 ≤ groups[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

batchSize=3, groups=[1,2,3,1,2]

Process

Arrange groups to maximize those starting with fresh donuts

Output

Maximum 4 groups can be happy

Key Takeaway

🎯 Key Insight: Group happiness depends only on remainder modulo batchSize - groups are happy when remainder=0

Asked in

G Google 8 M Microsoft 5

Brief HTML summary: The key insight is that only the remainder of each group size modulo batchSize matters. Groups are happy when they start with remainder 0. Best approach uses dynamic programming with memoization to explore all arrangements optimally. Time: O(batchSize^n), Space: O(batchSize^n)

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count with Greedy Pairing	O(n + k)	O(k)	Group customers by remainder and strategically pair complementary groups
Dynamic Programming with Memoization	O(batchSize^n)	O(batchSize^n)	Use recursive exploration with memoization to find optimal arrangement
Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all possible orderings and find the one with maximum happy groups

Frequency Count with Greedy Pairing — Algorithm Steps

Step 1: Convert all group sizes to remainders (group % batchSize)
Step 2: Count frequency of each remainder value
Step 3: Greedily pair complementary remainders and count maximum happy groups

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to Remainders

Transform group sizes to remainders mod batchSize

Count Frequencies

Count how many groups have each remainder

Pair Complements

Match groups whose remainders sum to batchSize

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int batchSize, int* groups, int n) {
    // Count frequency of each remainder
    int* remainders = (int*)calloc(batchSize, sizeof(int));
    for (int i = 0; i < n; i++) {
        remainders[groups[i] % batchSize]++;
    }
    
    // Groups with remainder 0 are always happy
    int happy = remainders[0];
    
    // Pair complementary remainders
    for (int i = 1; i <= (batchSize - 1) / 2; i++) {
        int complement = batchSize - i;
        if (i == complement) {
            happy += remainders[i] / 2;
        } else {
            happy += min(remainders[i], remainders[complement]);
        }
    }
    
    free(remainders);
    return happy;
}

int main() {
    int batchSize;
    scanf("%d", &batchSize);
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int groups[20];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        groups[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(batchSize, groups, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + k)

O(n) to process groups, O(k) to pair remainders where k is batchSize

✓ Linear Growth

Space Complexity

O(k)

Array to store frequency of each remainder (size batchSize)

✓ Linear Space

12.9K Views

Medium Frequency

~35 min Avg. Time

423 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count with Greedy Pairing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler