Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-066 · FOCUSED PRACTICE

Koko Eating Bananas — Minimum Feasible Rate

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 10768 deterministic checks. Learner drafts are not executed.

Understand the problem

Find the smallest positive integer eating rate that finishes all positive banana piles within hours. At most one pile is worked on per hour; a partial final hour cannot be used for a different pile. Return zero for no piles.

  • piles is nonnull with at most 100,000 entries, each a positive int. hours is a long. Nonpositive piles or hours<piles.length throw IllegalArgumentException; for an empty array, hours>=0 is valid and returns zero.
  • For nonempty piles and hours>=number of piles, a feasible rate exists at max(piles). Return the smallest rate k>=1 satisfying sum(ceil(pile/k))<=hours. The method does not reorder or mutate piles.
  • Null throws NullPointerException. Rate, pile, and midpoint values fit int; required hours accumulate in long using widened ceiling arithmetic. Baseline range enumeration is provided for bounded small inputs and is not suitable for int-maximum piles.

Examples

  1. Input: piles=[3,6,7,11], hours=8
    Output: 4

    At rate 4, hours per pile are [1,2,2,3], totaling 8; rate 3 needs 10.

  2. Input: piles=[30,11,23,4,20], hours=5
    Output: 30

    Only one hour per pile is available, forcing the largest pile to fit in one hour.

  3. Input: piles=[MAX], hours=2
    Output: 1,073,741,824

    ceil(MAX/2) rate is computed without an overflowing pile+rate−1 int expression.

  4. Input: piles=[], hours=0
    Output: 0

    The explicitly empty workload has no positive-rate requirement.

Before you start

  • Monotone feasibility versus witness search
  • Integer ceilings and widened accumulation

Recognize the structure

The desired rate is not an index in piles. It lies in an integer answer domain where faster rates never increase required hours. Prove the per-rate ceiling sum matches the one-pile-per-hour model, then binary-search its first feasible rate.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

No unsaved text changes · 130/20,000 characters

Self-review

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

For a candidate rate, exactly how many hours does each pile consume independently?

Hint 2

Why does increasing the rate preserve every feasible budget?

Hint 3

Validate H>=n, search [1,max pile], retain feasible midpoints, and use widened integer ceilings.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Try rates from one upward

Validate inputs, then enumerate k=1,2,… until the per-pile ceiling sum fits the budget. For [3,6,7,11], H=8, rates 1,2,3 need 27,15,10 hours, while rate 4 needs 8. This takes O(nM) worst-case work for M=max pile and O(1) workspace. It is useful on small numeric ranges but unacceptable when M approaches Integer.MAX_VALUE.

Improve the baseline

Prove bounds and feasibility

Every nonempty workload needs rate at least one. Rate M=max pile consumes exactly one hour per pile and is feasible precisely under the declared hours>=n assumption. Validate piles while finding M.

Use exact widened ceiling sums

For a positive pile, ceil(pile/k)=1+(pile−1)/k. Write pile−1L so arithmetic is long before division. Accumulate required hours in long; once a partial sum exceeds the budget, remaining positive contributions cannot restore feasibility.

Search for the first feasible rate

Maintain low=1,high=M with the smallest feasible rate in [low,high]. A feasible midpoint remains possible, so high=rate; an infeasible one and every smaller rate are excluded by low=rate+1.

Why it is correct

Predicate equals the model

A pile requires exactly ceil(pile/k) occupied hours. Since an hour cannot be shared between different piles, total required hours are the sum of these per-pile ceilings; using ceil(totalBananas/k) would model a different task.

Monotonicity and interval preservation

Each ceiling term is nonincreasing as k grows, so feasibility is false then true. If a midpoint is feasible, the first feasible rate is at most it; otherwise the answer is strictly larger. The initial maximum rate is a feasible witness.

Termination and arithmetic

Both updates strictly shrink the integer interval until low==high, the first feasible rate. Under 100,000 piles of positive int size, even the full rate-one sum is below 2.15×10^14, within long. Empty input returns zero before entering a positive-rate search.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    public static int minRate(int[] piles, long hours) {
        int maximum = validate(piles, hours);
        if (piles.length == 0) return 0;
        int low = 1, high = maximum;
        while (low < high) {
            int rate = low + (high - low) / 2;
            if (feasible(piles, hours, rate)) high = rate;
            else low = rate + 1;
        }
        return low;
    }
    private static int validate(int[] piles, long hours) {
        Objects.requireNonNull(piles, "piles");
        if (hours < piles.length) throw new IllegalArgumentException("fewer hours than piles");
        int maximum = 0;
        for (int pile : piles) {
            if (pile <= 0) throw new IllegalArgumentException("nonpositive pile");
            maximum = Math.max(maximum, pile);
        }
        return maximum;
    }
    private static boolean feasible(int[] piles, long hours, int rate) {
        long needed = 0;
        for (int pile : piles) {
            needed += 1L + (pile - 1L) / rate;
            if (needed > hours) return false;
        }
        return true;
    }
    public static int baseline(int[] piles, long hours) {
        validate(piles, hours);
        if (piles.length == 0) return 0;
        for (int rate = 1; ; rate++) {
            long needed = 0;
            for (int pile : piles) needed += pile / rate + (pile % rate == 0 ? 0L : 1L);
            if (needed <= hours) return rate;
        }
    }
}

Read the meaningful blocks

Validate rather than binary-search impossible input

hours<n cannot fit n positive piles at any rate, and zero/negative pile values break the stated model. These errors are detected before search.

Early exit is a lower-bound certificate

The feasible helper may stop after a prefix exceeds hours. Such a partial sum is not the full required-hours total; walkthroughs distinguish checked prefixes from complete sums.

Retain a feasible midpoint

Use high=rate, not rate−1. The midpoint may be exactly the minimum feasible rate and must remain a candidate.

Complexity

For n>0 and maximum pile M, validation costs O(n) and binary search uses O(n log(M+1)) worst-case time with O(1) auxiliary space. Early exits can reduce individual predicate work but do not change the worst-case bound.

The baseline is O(nM) worst-case time and O(1) space. Empty-input handling is O(1). Returned output is one int rate; no hourly schedule is constructed.

Exact-state walkthroughs

Reveal normal and boundary traces

Ceiling hours determine the first feasible rate

Input: {"piles":[3,6,7,11],"hours":8} · Minimum feasible rate: 4

Step 1 of 6: Validate piles and the feasible-budget contract.

For nonempty input, high=max pile is feasible because each pile then takes one hour. Empty workload returns zero.

Minimum rate — first feasible integer

Candidate rate range: [1, 11]. Budget: 8 hours.

  • pile 03not checked in this probe
  • pile 16not checked in this probe
  • pile 27not checked in this probe
  • pile 311not checked in this probe

No rate probe yet. Empty piles return zero; otherwise max pile is a feasible upper bound after validation.

State after this step
VariableValue
piles[3,6,7,11]
hours8
low1
high11
phase"rate"
See the affected Java block
 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int minRate(int[] piles, long hours) {
 5         int maximum = validate(piles, hours);
 6         if (piles.length == 0) return 0;
 7         int low = 1, high = maximum;
 8         while (low < high) {
 9             int rate = low + (high - low) / 2;
10             if (feasible(piles, hours, rate)) high = rate;
11             else low = rate + 1;
12         }
13         return low;
14     }
15     private static int validate(int[] piles, long hours) {
16         Objects.requireNonNull(piles, "piles");
17         if (hours < piles.length) throw new IllegalArgumentException("fewer hours than piles");
18         int maximum = 0;
19         for (int pile : piles) {
20             if (pile <= 0) throw new IllegalArgumentException("nonpositive pile");
21             maximum = Math.max(maximum, pile);
22         }
23         return maximum;
24     }
25     private static boolean feasible(int[] piles, long hours, int rate) {
26         long needed = 0;
27         for (int pile : piles) {
28             needed += 1L + (pile - 1L) / rate;
29             if (needed > hours) return false;
30         }
31         return true;
32     }
33     public static int baseline(int[] piles, long hours) {
34         validate(piles, hours);
35         if (piles.length == 0) return 0;
36         for (int rate = 1; ; rate++) {
37             long needed = 0;
38             for (int pile : piles) needed += pile / rate + (pile % rate == 0 ? 0L : 1L);
39             if (needed <= hours) return rate;
40         }
41     }
42 }
43

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Validate piles and the feasible-budget contract.

    For nonempty input, high=max pile is feasible because each pile then takes one hour. Empty workload returns zero.

    piles
    [3,6,7,11]
    hours
    8
    low
    1
    high
    11
    phase
    "rate"
  2. Retain the feasible rate as a possible first true answer.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [3,6,7,11]
    hours
    8
    low
    1
    high
    6
    phase
    "rate"
    before
    [1,11]
    rate
    6
    checkedCeilings
    [1,1,2,2]
    checked
    4
    complete
    true
    needed
    6
    feasible
    true
  3. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [3,6,7,11]
    hours
    8
    low
    4
    high
    6
    phase
    "rate"
    before
    [1,6]
    rate
    3
    checkedCeilings
    [1,2,3,4]
    checked
    4
    complete
    true
    needed
    10
    feasible
    false
  4. Retain the feasible rate as a possible first true answer.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [3,6,7,11]
    hours
    8
    low
    4
    high
    5
    phase
    "rate"
    before
    [4,6]
    rate
    5
    checkedCeilings
    [1,2,2,3]
    checked
    4
    complete
    true
    needed
    8
    feasible
    true
  5. Retain the feasible rate as a possible first true answer.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [3,6,7,11]
    hours
    8
    low
    4
    high
    4
    phase
    "rate"
    before
    [4,5]
    rate
    4
    checkedCeilings
    [1,2,2,3]
    checked
    4
    complete
    true
    needed
    8
    feasible
    true
  6. Return the documented value, index, boundary, range, or rate.

    The final result follows the problem-specific contract; the inputs were never mutated.

    result
    4

One extreme pile, two hours

Input: {"piles":[2147483647],"hours":2} · Minimum feasible rate: 1073741824

Step 1 of 33: Validate piles and the feasible-budget contract.

For nonempty input, high=max pile is feasible because each pile then takes one hour. Empty workload returns zero.

Minimum rate — first feasible integer

Candidate rate range: [1, 2147483647]. Budget: 2 hours.

  • pile 02147483647not checked in this probe

No rate probe yet. Empty piles return zero; otherwise max pile is a feasible upper bound after validation.

State after this step
VariableValue
piles[2147483647]
hours2
low1
high2147483647
phase"rate"
See the affected Java block
 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int minRate(int[] piles, long hours) {
 5         int maximum = validate(piles, hours);
 6         if (piles.length == 0) return 0;
 7         int low = 1, high = maximum;
 8         while (low < high) {
 9             int rate = low + (high - low) / 2;
10             if (feasible(piles, hours, rate)) high = rate;
11             else low = rate + 1;
12         }
13         return low;
14     }
15     private static int validate(int[] piles, long hours) {
16         Objects.requireNonNull(piles, "piles");
17         if (hours < piles.length) throw new IllegalArgumentException("fewer hours than piles");
18         int maximum = 0;
19         for (int pile : piles) {
20             if (pile <= 0) throw new IllegalArgumentException("nonpositive pile");
21             maximum = Math.max(maximum, pile);
22         }
23         return maximum;
24     }
25     private static boolean feasible(int[] piles, long hours, int rate) {
26         long needed = 0;
27         for (int pile : piles) {
28             needed += 1L + (pile - 1L) / rate;
29             if (needed > hours) return false;
30         }
31         return true;
32     }
33     public static int baseline(int[] piles, long hours) {
34         validate(piles, hours);
35         if (piles.length == 0) return 0;
36         for (int rate = 1; ; rate++) {
37             long needed = 0;
38             for (int pile : piles) needed += pile / rate + (pile % rate == 0 ? 0L : 1L);
39             if (needed <= hours) return rate;
40         }
41     }
42 }
43

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Validate piles and the feasible-budget contract.

    For nonempty input, high=max pile is feasible because each pile then takes one hour. Empty workload returns zero.

    piles
    [2147483647]
    hours
    2
    low
    1
    high
    2147483647
    phase
    "rate"
  2. Retain the feasible rate as a possible first true answer.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1
    high
    1073741824
    phase
    "rate"
    before
    [1,2147483647]
    rate
    1073741824
    checkedCeilings
    [2]
    checked
    1
    complete
    true
    needed
    2
    feasible
    true
  3. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    536870913
    high
    1073741824
    phase
    "rate"
    before
    [1,1073741824]
    rate
    536870912
    checkedCeilings
    [4]
    checked
    1
    complete
    true
    needed
    4
    feasible
    false
  4. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    805306369
    high
    1073741824
    phase
    "rate"
    before
    [536870913,1073741824]
    rate
    805306368
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  5. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    939524097
    high
    1073741824
    phase
    "rate"
    before
    [805306369,1073741824]
    rate
    939524096
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  6. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1006632961
    high
    1073741824
    phase
    "rate"
    before
    [939524097,1073741824]
    rate
    1006632960
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  7. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1040187393
    high
    1073741824
    phase
    "rate"
    before
    [1006632961,1073741824]
    rate
    1040187392
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  8. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1056964609
    high
    1073741824
    phase
    "rate"
    before
    [1040187393,1073741824]
    rate
    1056964608
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  9. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1065353217
    high
    1073741824
    phase
    "rate"
    before
    [1056964609,1073741824]
    rate
    1065353216
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  10. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1069547521
    high
    1073741824
    phase
    "rate"
    before
    [1065353217,1073741824]
    rate
    1069547520
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  11. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1071644673
    high
    1073741824
    phase
    "rate"
    before
    [1069547521,1073741824]
    rate
    1071644672
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  12. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1072693249
    high
    1073741824
    phase
    "rate"
    before
    [1071644673,1073741824]
    rate
    1072693248
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  13. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073217537
    high
    1073741824
    phase
    "rate"
    before
    [1072693249,1073741824]
    rate
    1073217536
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  14. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073479681
    high
    1073741824
    phase
    "rate"
    before
    [1073217537,1073741824]
    rate
    1073479680
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  15. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073610753
    high
    1073741824
    phase
    "rate"
    before
    [1073479681,1073741824]
    rate
    1073610752
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  16. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073676289
    high
    1073741824
    phase
    "rate"
    before
    [1073610753,1073741824]
    rate
    1073676288
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  17. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073709057
    high
    1073741824
    phase
    "rate"
    before
    [1073676289,1073741824]
    rate
    1073709056
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  18. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073725441
    high
    1073741824
    phase
    "rate"
    before
    [1073709057,1073741824]
    rate
    1073725440
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  19. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073733633
    high
    1073741824
    phase
    "rate"
    before
    [1073725441,1073741824]
    rate
    1073733632
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  20. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073737729
    high
    1073741824
    phase
    "rate"
    before
    [1073733633,1073741824]
    rate
    1073737728
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  21. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073739777
    high
    1073741824
    phase
    "rate"
    before
    [1073737729,1073741824]
    rate
    1073739776
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  22. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073740801
    high
    1073741824
    phase
    "rate"
    before
    [1073739777,1073741824]
    rate
    1073740800
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  23. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741313
    high
    1073741824
    phase
    "rate"
    before
    [1073740801,1073741824]
    rate
    1073741312
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  24. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741569
    high
    1073741824
    phase
    "rate"
    before
    [1073741313,1073741824]
    rate
    1073741568
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  25. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741697
    high
    1073741824
    phase
    "rate"
    before
    [1073741569,1073741824]
    rate
    1073741696
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  26. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741761
    high
    1073741824
    phase
    "rate"
    before
    [1073741697,1073741824]
    rate
    1073741760
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  27. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741793
    high
    1073741824
    phase
    "rate"
    before
    [1073741761,1073741824]
    rate
    1073741792
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  28. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741809
    high
    1073741824
    phase
    "rate"
    before
    [1073741793,1073741824]
    rate
    1073741808
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  29. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741817
    high
    1073741824
    phase
    "rate"
    before
    [1073741809,1073741824]
    rate
    1073741816
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  30. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741821
    high
    1073741824
    phase
    "rate"
    before
    [1073741817,1073741824]
    rate
    1073741820
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  31. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741823
    high
    1073741824
    phase
    "rate"
    before
    [1073741821,1073741824]
    rate
    1073741822
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  32. Reject this rate using the checked hours prefix.

    needed is the complete per-pile ceiling sum. The smallest feasible rate stays within [low,high].

    piles
    [2147483647]
    hours
    2
    low
    1073741824
    high
    1073741824
    phase
    "rate"
    before
    [1073741823,1073741824]
    rate
    1073741823
    checkedCeilings
    [3]
    checked
    1
    complete
    true
    needed
    3
    feasible
    false
  33. Return the documented value, index, boundary, range, or rate.

    The final result follows the problem-specific contract; the inputs were never mutated.

    result
    1073741824

Empty workload returns zero

Input: {"piles":[],"hours":0} · Minimum feasible rate: 0

Step 1 of 2: Validate piles and the feasible-budget contract.

For nonempty input, high=max pile is feasible because each pile then takes one hour. Empty workload returns zero.

Minimum rate — first feasible integer

Candidate rate range: [0, 0]. Budget: 0 hours.

    No rate probe yet. Empty piles return zero; otherwise max pile is a feasible upper bound after validation.

    State after this step
    VariableValue
    piles[]
    hours0
    low0
    high0
    phase"rate"
    See the affected Java block
     1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int minRate(int[] piles, long hours) {
 5         int maximum = validate(piles, hours);
 6         if (piles.length == 0) return 0;
 7         int low = 1, high = maximum;
 8         while (low < high) {
 9             int rate = low + (high - low) / 2;
10             if (feasible(piles, hours, rate)) high = rate;
11             else low = rate + 1;
12         }
13         return low;
14     }
15     private static int validate(int[] piles, long hours) {
16         Objects.requireNonNull(piles, "piles");
17         if (hours < piles.length) throw new IllegalArgumentException("fewer hours than piles");
18         int maximum = 0;
19         for (int pile : piles) {
20             if (pile <= 0) throw new IllegalArgumentException("nonpositive pile");
21             maximum = Math.max(maximum, pile);
22         }
23         return maximum;
24     }
25     private static boolean feasible(int[] piles, long hours, int rate) {
26         long needed = 0;
27         for (int pile : piles) {
28             needed += 1L + (pile - 1L) / rate;
29             if (needed > hours) return false;
30         }
31         return true;
32     }
33     public static int baseline(int[] piles, long hours) {
34         validate(piles, hours);
35         if (piles.length == 0) return 0;
36         for (int rate = 1; ; rate++) {
37             long needed = 0;
38             for (int pile : piles) needed += pile / rate + (pile % rate == 0 ? 0L : 1L);
39             if (needed <= hours) return rate;
40         }
41     }
42 }
43

    Highlight locates the relevant statement or block; one trace step may summarize several assignments.

    Read the full static trace
    1. Validate piles and the feasible-budget contract.

      For nonempty input, high=max pile is feasible because each pile then takes one hour. Empty workload returns zero.

      piles
      []
      hours
      0
      low
      0
      high
      0
      phase
      "rate"
    2. Return the documented value, index, boundary, range, or rate.

      The final result follows the problem-specific contract; the inputs were never mutated.

      result
      0

    Test the contract

    1. Input: [], H=0
      Output: 0

      Empty workload policy.

    2. Input: [3,6,7,11], H=8
      Output: 4

      Classic rounding boundaries.

    3. Input: [MAX], H=2
      Output: 1,073,741,824

      Wide ceiling arithmetic.

    4. Input: n piles, H=n
      Output: max pile

      Tight one-hour-per-pile budget.

    5. Input: [1,2], H=1; [0], H=1
      Output: IllegalArgumentException

      Infeasible budget and invalid pile.

    Common mistakes and counterexamples

    Use ceil(sum/k) instead of a sum of ceilings

    Counterexample: Two piles [1,1] at rate 2 still need two separate hours, not one.

    Apply the ceiling separately to each pile.

    Compute (pile+rate−1) using int

    Counterexample: A MAX pile with a large rate can overflow the numerator.

    Use 1L+(pile−1L)/rate or another explicitly widened formula.

    Let infeasible hours silently search

    Counterexample: H<n has no feasible positive rate, so max pile is not a valid upper witness.

    Reject before initializing the binary search.

    Present an early-exit prefix sum as total hours

    Counterexample: A predicate can return false after only part of the workload.

    Record checked pile count, partial sum, and completion flag separately in traces.

    Follow-ups

    Return a schedule as well as the rate.

    After finding k, emit each pile’s occupied-hour count or a compressed allocation. A literal hour-by-hour schedule can be much larger than the input and requires an output-size bound.

    Hours may be shared between piles.

    Then sum-of-ceilings is no longer the correct predicate. If arbitrary switching within an hour is allowed, total work may be modeled by ceil(total/k); rederive the model before reusing the search.

    Use another resource-rate problem.

    Identify the exact feasibility function, prove monotonicity and a feasible upper bound, and audit rounding/overflow. Shipping capacity also needs a separate greedy-predicate proof rather than these independent ceilings.

    Related foundations

    Keep practicing

    Return to the lesson

    AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.