EF-T04: Minimum Ordered Batch Capacity

Exercise contract#

A packaging line receives positive integer item weights in order. Place consecutive items into nonempty batches, preserving item order and never splitting an item. You may use at most b batches. Return the smallest capacity sufficient for every batch, where a batch's load is the sum of its items. b must be a positive integer. Empty input returns 0. Reject b < 1 or any nonpositive weight.

Constraints

• 0 <= number of weights <= 100,000.
• For nonempty input, every weight is an integer in [1, 1,000,000,000].
• b is an integer with b >= 1; fewer than b nonempty batches are allowed.
• Items cannot be split or reordered, and each used batch contains consecutive items.
• The total can reach 100,000,000,000,000, so Java uses long for capacities, sums, and midpoint arithmetic.

Examples

weights=[4,2,5,3], b=2

8Capacity 8 fits [4,2] and [5,3]. Capacity 7 needs three batches, so 8 is the first feasible capacity.

weights=[], b=2

0There are no items and therefore no nonempty batch to load.

Derive the approach#

Baseline: Try every integer capacity from the largest item through the total sum. For each capacity, scan the weights greedily to count required batches. This is correct but can scan a very large numeric range.

1. Any capacity below the largest weight is impossible because items cannot be split.
2. The total sum is feasible in one batch, so it is a valid upper bound.
3. For a fixed capacity, fill the current batch until the next item would exceed it, then open a new batch.
4. Because every weight is positive, ending a batch before the next item stops fitting cannot reduce the number of batches needed; the greedy check uses the fewest batches for that capacity.
5. If capacity c works, every larger capacity also works, so feasible capacities form a suffix.
6. Binary-search the first feasible capacity. Keep a feasible midpoint as the upper bound; discard an infeasible midpoint and every smaller capacity.

Time

For nonempty input, O(n * (1 + log(S - M + 1))) in the unit-cost arithmetic model, where n is the item count, S is total weight, and M is the maximum weight; empty input is O(1).

Space

O(1) auxiliary state beyond the input.

Assumptions

Weights are strictly positive, batches may be fewer than b, sums and midpoint arithmetic fit the declared numeric model, and the linear term includes validation plus initial maximum/total scans even when only one capacity is possible.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

def minimum_capacity(weights, batches):
    if type(batches) is not int or batches < 1:
        raise ValueError("positive weights and batches >= 1 required")
    if any(type(weight) is not int or weight <= 0 for weight in weights):
        raise ValueError("positive weights and batches >= 1 required")
    if not weights:
        return 0

    def fits(capacity):
        used = 1
        current = 0
        for weight in weights:
            if current + weight > capacity:
                used += 1
                current = 0
            current += weight
        return used <= batches

    low, high = max(weights), sum(weights)
    while low < high:
        middle = low + (high - low) // 2
        if fits(middle):
            high = middle
        else:
            low = middle + 1
    return low

static long minimumCapacity(long[] weights, int batches) {
    if (batches < 1) {
        throw new IllegalArgumentException("positive weights and batches >= 1 required");
    }
    if (weights.length == 0) return 0L;

    long low = 0L;
    long high = 0L;
    for (long weight : weights) {
        if (weight <= 0L) {
            throw new IllegalArgumentException("positive weights and batches >= 1 required");
        }
        low = Math.max(low, weight);
        high = Math.addExact(high, weight);
    }

    while (low < high) {
        long middle = low + (high - low) / 2L;
        if (fits(weights, batches, middle)) high = middle;
        else low = middle + 1L;
    }
    return low;
}

static boolean fits(long[] weights, int batches, long capacity) {
    int used = 1;
    long current = 0L;
    for (long weight : weights) {
        if (current + weight > capacity) {
            used += 1;
            current = 0L;
        }
        current += weight;
    }
    return used <= batches;
}

Deterministic test plan#

Transfer and follow-ups#

• If item reordering is allowed, the consecutive greedy proof no longer defines the same problem; compare it with a scheduling or bin-packing contract.
• If zero or negative weights are allowed, re-examine both the greedy minimum-batch proof and capacity monotonicity before reusing the search.
• Return one optimal partition and explain the added output storage and deterministic cut policy.

Narrate: I can test a capacity greedily in one pass; feasibility is monotonic; my inclusive bounds retain the first capacity that works.

Authorship and review#

Original Engineering Foundry prompt, examples, explanations, and verification programs using standard algorithmic techniques. This is not attributed to an employer and is not evidence of interview frequency.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09