Koko Eating Bananas leetcode

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.


Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.


Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.


Return the minimum integer k such that she can eat all the bananas within h hours.


 


Example 1:


Input: piles = [3,6,7,11], h = 8

Output: 4

Example 2:


Input: piles = [30,11,23,4,20], h = 5

Output: 30

Example 3:


Input: piles = [30,11,23,4,20], h = 6

Output: 23



class Solution {

    // Helper function to find maximum pile value
    public static int maxsum(int [] arr) {
        int sum = 0;
        for (int a : arr) {
            sum = sum + a;
        }
        return sum;
    }

    public int minEatingSpeed(int[] piles, int h) {

        int n = piles.length;

        int start = 1; // Minimum eating speed can be 1 banana per hour
        int end = 0;   // We will find maximum pile value to set as the maximum possible eating speed
       
        // Find the maximum value from piles
        for (int pile : piles) {
            end = Math.max(end, pile);
        }

        int ans = 0; // To store the minimum speed found

        // Standard binary search
        while (start <= end) {
            int mid = start + (end - start) / 2; // Current speed to test

            int hourcount = 0; // To count how many total hours needed at speed = mid

            for (int i = 0; i < n; i++) {
                // Each pile requires pile[i]/mid hours (rounded up)
                hourcount += piles[i] / mid;

                // If there is a remainder, we need one more hour
                if (piles[i] % mid != 0) {
                    hourcount++;
                }
            }

            // Now check if total hours needed is within h
            if (hourcount > h) {
                // Need more hours than allowed, so speed is too slow → increase speed
                start = mid + 1;
            } else {
                // Speed is enough (or more), try to find smaller valid speed
                ans = mid;
                end = mid - 1;
            }
        }

        return ans;
    }
}

 

Comments

Post a Comment

Popular posts from this blog

Two Sum II - Input Array Is Sorted

 Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order , find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space .   Example 1: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2]. Example 2: Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3]. Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1,...
Read more

Comparable Vs. Comparator in Java

  In Java , Comparable and Comparator both are interfaces used to sort objects. Comparable It defines  natural ordering  within a class. It is implemented  inside  the class being sorted. It uses the compareTo() method. It allows sorting  by one one . Comparable provides a  single sorting sequence . In other words, we can sort the collection on the basis of a single element such as id, name, and price. Comparable  affects the original class , i.e., the actual class is modified. Comparable is present in  java.lang  package. We can sort the list elements of Comparable type by  Collections.sort(List)  method. Only one compareTo() method can be implemented, restricting flexibility. Comparator It defines  custom sorting logic It is implemented  in a separate class  or using lambda expressions . It uses the compare() method. It allows sorting  by multiple criteria . The Comparator provides  multiple sorting...
Read more

Increasing Triplet Subsequence

 Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.   Example 1: Input: nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid. Example 2: Input: nums = [5,4,3,2,1] Output: false Explanation: No triplet exists. Example 3: Input: nums = [2,1,5,0,4,6] Output: true Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6. Brute Force : Failed for some testcase class Solution {     public boolean increasingTriplet ( int [] nums ) {         int n = nums . length ;         int i = 0 ;         int j =i+ 1 ;         int k =j+ 1 ;         while (i <n && j<n && k<n)         {         if (nums...
Read more