Interview 150
Koko Eating Bananas
- Problem
- LC 875
- File
- interview150_LC875KokoEatingBananas.java
- Path
- pkg5leetcode/interview150/interview150_LC875KokoEatingBananas.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC875KokoEatingBananas.java
- Approach
- Binary search minimum eating speed; check hours needed.
- Complexity
- Time O(n log max), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Koko Eating Bananas | LC 8755 * APPROACH: Binary search minimum eating speed; check hours needed.6 * COMPLEXITY: Time O(n log max), Space O(1)7 */8public class interview150_LC875KokoEatingBananas {9 static int minEatingSpeed(int[] piles, int h) {10 int lo = 1, hi = 0;11 for (int p : piles) hi = Math.max(hi, p);12 while (lo < hi) {13 int mid = lo + (hi - lo) / 2;14 if (hours(piles, mid) <= h) hi = mid;15 else lo = mid + 1;16 }17 return lo;18 }19 20 static long hours(int[] piles, int speed) {21 long h = 0;22 for (int p : piles) h += (p + speed - 1) / speed;23 return h;24 }25 26 public static void main(String[] args) {27 check(minEatingSpeed(new int[]{3, 6, 7, 11}, 8) == 4, "case1");28 check(minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 5) == 30, "case2");29 System.out.println("all tests passed");30 }31 32 static void check(boolean cond, String name) {33 if (!cond) throw new AssertionError("FAILED: " + name);34 System.out.println(" PASS " + name);35 }36}