Maximum Number of Groups Getting Fresh Donuts

Hard
1624.

Maximum Number of Groups Getting Fresh Donuts

Maximum Number of Groups Getting Fresh Donuts is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Google interviews.

A donut shop bakes donuts in batches of exactly batchSize, and it never starts a new batch until every donut of the current batch has been served. Groups of customers arrive: group i has groups[i] people, and all members of a group are served one after another before the next group begins. Every customer gets one donut.

A group is happy if its first customer receives a freshly baked donut — that is, the batch in progress had no donuts left over from earlier customers when this group started.

You may arrange the groups in any order. Return the maximum possible number of happy groups.

Example 1

Input
batchSize = 3, groups = [1,2,3,4,5,6]
Output
4
Explanation
One good order is [6,2,4,5,1,3]: groups 6, 2, 4 and 1 each start on a fresh batch.

Example 2

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

Example 3

Input
batchSize = 1, groups = [7,7,7]
Output
3
Explanation
With batches of one donut, every group starts fresh.

Constraints

  • 1 <= batchSize <= 9
  • 1 <= groups.length <= 30
  • 1 <= groups[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} batchSize
 * @param {number[]} groups
 * @return {number}
 */
var maxHappyGroups = function(batchSize, groups) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Groups Getting Fresh Donuts — Solution

Maximum Number of Groups Getting Fresh Donuts solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Groups Getting Fresh Donuts is a hard coding problem on arrays, dynamic programming and bit manipulation, asked in Google interviews.

Problem statement

A donut shop bakes donuts in batches of exactly batchSize, and it never starts a new batch until every donut of the current batch has been served. Groups of customers arrive: group i has groups[i] people, and all members of a group are served one after another before the next group begins. Every customer gets one donut.

A group is happy if its first customer receives a freshly baked donut — that is, the batch in progress had no donuts left over from earlier customers when this group started.

You may arrange the groups in any order. Return the maximum possible number of happy groups.

Example 1

Input: batchSize = 3, groups = [1,2,3,4,5,6]
Output: 4
Explanation: One good order is [6,2,4,5,1,3]: groups 6, 2, 4 and 1 each start on a fresh batch.

Example 2

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

Example 3

Input: batchSize = 1, groups = [7,7,7]
Output: 3
Explanation: With batches of one donut, every group starts fresh.

Constraints

  • 1 <= batchSize <= 9
  • 1 <= groups.length <= 30
  • 1 <= groups[i] <= 10^9

Hints for Maximum Number of Groups Getting Fresh Donuts

  1. Hint 1

    Only groups[i] % batchSize matters. Groups whose size is a multiple of batchSize can all go first, and each of them is happy.

  2. Hint 2

    A group with remainder r followed by one with remainder batchSize - r brings the leftover back to zero: greedily pair them up, each pair contributing one happy group.

  3. Hint 3

    What remains is small: count how many groups of each remainder are left and search over those counts, where the leftover is fixed by which groups have been served. Memoise on the counts.

How to solve Maximum Number of Groups Getting Fresh Donuts

Reduce every group to its remainder modulo batchSize. The state of the arrangement is then just how many groups of each remainder are still waiting — the current leftover is determined by what has been served. Greedy pairing of complementary remainders shrinks that state space to a few thousand.

Approach

  1. Count cnt[r] groups per remainder. Start with answer = cnt[0] (they go first, each happy).
  2. For r < batchSize - r, pair p = min(cnt[r], cnt[batchSize - r]) groups: each pair adds 1. For r == batchSize - r, pairs within the class add cnt[r] / 2. Remove the paired groups.
  3. Encode the remaining counts as a mixed-radix index; dp[u] is the most happy groups among the groups used in state u. Iterate states in increasing order; the served sum modulo batchSize tells whether the next group is happy.
  4. Return answer + dp[all used].

Why it works

A group is happy exactly when the remainders served before it sum to 0 modulo batchSize, so the outcome depends only on the multiset of remainders served, which the count vector captures. Pairing complementary remainders is safe: in any arrangement, rearranging so each such pair is adjacent never loses a happy group, since a pair restores the leftover to zero and contributes one happy start. After pairing, at most one of each complementary pair of classes is non-empty, so the remaining state count is tiny.

Complexity

  • Time — O(S * batchSize) where S is the number of count vectors (a few thousand)
  • Space — O(S)

Pitfalls

  • Large group sizes (up to 10^9) only matter modulo batchSize; never simulate donuts.
  • Remainder classes with r == batchSize - r pair with themselves.
  • The first group served is always happy, even after the zero-remainder groups.

Reference solution

Python

from typing import List

def maxHappyGroups(batchSize: int, groups: List[int]) -> int:
    b = batchSize
    cnt = [0] * b
    for g in groups:
        cnt[g % b] += 1
    ans = cnt[0]
    for r in range(1, b):
        s = b - r
        if r < s:
            p = min(cnt[r], cnt[s])
            ans += p
            cnt[r] -= p
            cnt[s] -= p
        elif r == s:
            ans += cnt[r] // 2
            cnt[r] %= 2
    stride = [0] * b
    total = 1
    for r in range(1, b):
        stride[r] = total
        total *= cnt[r] + 1
    dp = [0] * total
    for idx in range(total):
        used = [(idx // stride[r]) % (cnt[r] + 1) if r else 0 for r in range(b)]
        happy = 1 if sum(used[r] * r for r in range(b)) % b == 0 else 0
        cur = dp[idx] + happy
        for r in range(1, b):
            if used[r] < cnt[r] and cur > dp[idx + stride[r]]:
                dp[idx + stride[r]] = cur
    return ans + dp[total - 1]

Java

public static int maxHappyGroups(int batchSize, int[] groups) {
    int b = batchSize;
    int[] cnt = new int[b];
    for (int g : groups) cnt[g % b]++;
    int ans = cnt[0];
    for (int r = 1; r < b; r++) {
        int s = b - r;
        if (r < s) {
            int p = Math.min(cnt[r], cnt[s]);
            ans += p; cnt[r] -= p; cnt[s] -= p;
        } else if (r == s) {
            ans += cnt[r] / 2;
            cnt[r] %= 2;
        }
    }
    int[] stride = new int[b];
    int total = 1;
    for (int r = 1; r < b; r++) { stride[r] = total; total *= cnt[r] + 1; }
    int[] dp = new int[total], used = new int[b];
    for (int idx = 0; idx < total; idx++) {
        int sum = 0;
        for (int r = 1; r < b; r++) {
            used[r] = (idx / stride[r]) % (cnt[r] + 1);
            sum += used[r] * r;
        }
        int cur = dp[idx] + (sum % b == 0 ? 1 : 0);
        for (int r = 1; r < b; r++) {
            if (used[r] < cnt[r] && cur > dp[idx + stride[r]]) dp[idx + stride[r]] = cur;
        }
    }
    return ans + dp[total - 1];
}

C++

int maxHappyGroups(int batchSize, vector<int>& groups) {
    int b = batchSize;
    vector<int> cnt(b, 0);
    for (int g : groups) cnt[g % b]++;
    int ans = cnt[0];
    for (int r = 1; r < b; r++) {
        int s = b - r;
        if (r < s) {
            int p = min(cnt[r], cnt[s]);
            ans += p; cnt[r] -= p; cnt[s] -= p;
        } else if (r == s) {
            ans += cnt[r] / 2;
            cnt[r] %= 2;
        }
    }
    vector<int> stride(b, 0), used(b, 0);
    int total = 1;
    for (int r = 1; r < b; r++) { stride[r] = total; total *= cnt[r] + 1; }
    vector<int> dp(total, 0);
    for (int idx = 0; idx < total; idx++) {
        int sum = 0;
        for (int r = 1; r < b; r++) {
            used[r] = (idx / stride[r]) % (cnt[r] + 1);
            sum += used[r] * r;
        }
        int cur = dp[idx] + (sum % b == 0 ? 1 : 0);
        for (int r = 1; r < b; r++) {
            if (used[r] < cnt[r] && cur > dp[idx + stride[r]]) dp[idx + stride[r]] = cur;
        }
    }
    return ans + dp[total - 1];
}

JavaScript

var maxHappyGroups = function(batchSize, groups) {
    var b = batchSize, cnt = new Array(b).fill(0);
    for (var i = 0; i < groups.length; i++) cnt[groups[i] % b]++;
    var ans = cnt[0];
    for (var r = 1; r < b; r++) {
        var s = b - r;
        if (r < s) {
            var p = Math.min(cnt[r], cnt[s]);
            ans += p; cnt[r] -= p; cnt[s] -= p;
        } else if (r === s) {
            ans += Math.floor(cnt[r] / 2);
            cnt[r] %= 2;
        }
    }
    var stride = new Array(b).fill(0), total = 1;
    for (var r = 1; r < b; r++) { stride[r] = total; total *= cnt[r] + 1; }
    var dp = new Array(total).fill(0), used = new Array(b).fill(0);
    for (var idx = 0; idx < total; idx++) {
        var sum = 0;
        for (var r = 1; r < b; r++) {
            used[r] = Math.floor(idx / stride[r]) % (cnt[r] + 1);
            sum += used[r] * r;
        }
        var cur = dp[idx] + (sum % b === 0 ? 1 : 0);
        for (var r = 1; r < b; r++) {
            if (used[r] < cnt[r] && cur > dp[idx + stride[r]]) dp[idx + stride[r]] = cur;
        }
    }
    return ans + dp[total - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming