CodingGyan

Minimum Eating Speed (Binary Search on the Answer)

hard Searching and Sorting

Problem

There are piles of bananas. A monkey eats at a speed of s bananas per hour. In one hour it chooses one pile and eats up to s bananas from it (if the pile has fewer, it eats the whole pile and does nothing else in that hour). Find the smallest whole speed s so that the monkey finishes all piles in at most h hours. The number of piles is at most h.

Constraints

  • 1 <= n <= h <= 10^6
  • 1 <= pile <= 10^9

Examples

Input

4
3 6 7 11
8

Output

4

Solutions

Best approachTime O(n log max)Space O(1)

We do not search in the array. We search in the space of possible answers, because 'fast enough' is true for all speeds from some value up (a monotone rule). Each check costs O(n), and there are O(log max) checks.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Smallest speed.
 * Input   : n, the piles, then h.
 * Output  : The speed.
 * Approach: Binary search on s.
 * Time    : O(n log max)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(int[] a, int k) {
        // Step 1: The answer is between 1 and the biggest pile. A bigger speed never needs more hours, so we can binary search.
        int low = 1;
        int high = 1;
        for (int pile : a) {
            high = Math.max(high, pile);
        }
        while (low < high) {
            int middle = low + (high - low) / 2;
            // Step 2: Count the hours that speed "middle" needs. Each pile takes ceil(pile / middle) hours.
            long hours = 0;
            for (int pile : a) {
                hours += (pile + middle - 1) / middle;
            }
            // Step 3: If this speed is fast enough, try slower speeds too. Otherwise we must go faster.
            if (hours <= k) {
                high = middle;
            } else {
                low = middle + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(solve(a, k));
    }
}
Hints (1)
  1. Why is the rule 'speed s is fast enough' monotone?

Try these next