Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Binary Search

Koko Eating Bananas

Medium · Binary Search · Asked at Google, Amazon, Meta

There are n piles of bananas. Koko eats at speed k bananas per hour: each hour she picks one pile and eats k bananas from it (or the whole pile if it has fewer). Find the minimum k so she finishes all piles within h hours.

Input

First line: n. Second line: n pile sizes. Third line: h.

Output

The minimum eating speed k.

Constraints

Binary search on k. Hours needed at speed k = Σ ⌈pile / k⌉.

Example 1

Input

4
3 6 7 11
8

Output

4

Example 2

Input

5
30 11 23 4 20
5

Output

30

Hints

  1. If Koko can finish at speed k, she can also finish at any faster speed — the answer is monotonic.
  2. Binary search k in [1, max pile]. Hours at speed k = Σ ceil(pile / k) = Σ (pile + k − 1) / k.

Approach

Searching on the answer: hours(k) decreases as k grows, so find the smallest k with hours(k) <= h. The range is 1 to max(pile), because at max(pile) every pile takes exactly one hour. Each check is O(n). The hour total can reach 10^4 × 10^9, so it needs 64 bits.

Complexity: O(n log(max pile)) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> piles(n);
    for (auto &p : piles) cin >> p;
    long long h;
    cin >> h;
    long long lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        long long k = lo + (hi - lo) / 2, hours = 0;
        for (long long p : piles) hours += (p + k - 1) / k;
        if (hours <= h) hi = k;
        else lo = k + 1;
    }
    cout << lo << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
piles, h = data[1 : n + 1], data[n + 1]
lo, hi = 1, max(piles)
while lo < hi:
    k = (lo + hi) // 2
    hours = sum((p + k - 1) // k for p in piles)
    if hours <= h:
        hi = k
    else:
        lo = k + 1
print(lo)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] piles = new long[n];
        long hi = 1;
        for (int i = 0; i < n; i++) {
            piles[i] = sc.nextLong();
            hi = Math.max(hi, piles[i]);
        }
        long h = sc.nextLong(), lo = 1;
        while (lo < hi) {
            long k = lo + (hi - lo) / 2, hours = 0;
            for (long p : piles) hours += (p + k - 1) / k;
            if (hours <= h) hi = k;
            else lo = k + 1;
        }
        System.out.println(lo);
    }
}

Solve Koko Eating Bananas online · All practice problems