Koko eating bananas

Intuition:

The straightforward solution for this problem is to use linear search algorithm to to check all possible answers from 1 to max, where max is the maximum element of the array. The minimum number for which the required time is less than or equal to h, is our required answer.

Approach:

Working of minimumRateToEatBananas(nums, h):

First find out the maximum element in array by calling the 'findMax()'.
Then , iterate from 1 to max which signifies the number of bananas eaten per hour, and for each iteration find out the hour taken to eat those bananas by calling calculateToatalHours ().
If the calculated hour is less than or equal to given limit, return the current value of iteration(number of bananas) as an answer.
If no suitable answer is found, return max element as an answer.

Working of findMax(arr):

First initialize a variable 'maxi', which will store maximum element of the array.
Now, literate through the array and find the maximum element among them, and return it.

Working of calculateTotalHours(arr,hourly):

Start with initializing n = size of array, which gives the number of elements in the array. Initialize 'totalH' to 0, which will accumulate the total hours required. 'hourly' represents the number of items that can be processed per hour.
Compute the number of hours required to eat all bananas at the rate of 'hourly' bananas per hour and store in 'totalH'. Use ceil function to round up the division result to ensure that partial hours are counted correctly when necessary. Ater the traversal has ended, return 'totalH' as answer.

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

class Solution {
private:
    // Helper function to find the maximum element in the vector 
    int findMax(vector<int> &v) {
        int maxi = INT_MIN;
        int n = v.size();
        
        // Find the maximum element
        for (int i = 0; i < n; i++) {
            maxi = max(maxi, v[i]);
        }
        return maxi;
    }

    /* Helper function to calculate total hours
    required at given hourly rate */
    long long calculateTotalHours(vector<int> &v, int hourly) {
        long long totalH = 0;
        int n = v.size();
        
        // Calculate total hours required
        for (int i = 0; i < n; i++) {
            totalH += ceil((double)(v[i]) / (double)(hourly));
        }
        return totalH;
    }

public:
    // Function to find the minimum rate to eat bananas 
    int minimumRateToEatBananas(vector<int> nums, int h) {
        // Find the maximum number of bananas
        int maxi = findMax(nums);

        /* Find the minimum value of k
        that satisfies the condition*/
        for (int i = 1; i <= maxi; i++) {
            long long reqTime = calculateTotalHours(nums, i);
            if (reqTime <= (long long)h) {
                return i;
            }
        }

        /* Dummy return statement (should 
        not be reached in valid cases)*/
        return maxi;
    }
};

int main() {
    vector<int> v = {7, 15, 6, 3};
    int h = 8;

    // Create an object of the Solution class
    Solution sol;

    int ans = sol.minimumRateToEatBananas(v, h);

    // Print the result
    cout << "Koko should eat at least " << ans << " bananas/hr.\n";

    return 0;
}
import java.util.*;

class Solution {
    // Helper function to find the maximum element in the array
    private int findMax(int[] v) {
        int maxi = Integer.MIN_VALUE;
        int n = v.length;

        // Find the maximum element
        for (int i = 0; i < n; i++) {
            maxi = Math.max(maxi, v[i]);
        }
        return maxi;
    }

    /* Helper function to calculate total hours
       required at given hourly rate */
    private long calculateTotalHours(int[] v, int hourly) {
        long totalH = 0;
        int n = v.length;

        // Calculate total hours required
        for (int i = 0; i < n; i++) {
            totalH += Math.ceil((double) v[i] / (double) hourly);
        }
        return totalH;
    }

    // Function to find the minimum rate to eat bananas
    public int minimumRateToEatBananas(int[] nums, int h) {
        // Find the maximum number of bananas
        int maxi = findMax(nums);

        /* Find the minimum value of k
           that satisfies the condition */
        for (int i = 1; i <= maxi; i++) {
            long reqTime = calculateTotalHours(nums, i);
            if (reqTime <= (long) h) {
                return i;
            }
        }

        /* Dummy return statement (should 
           not be reached in valid cases) */
        return maxi;
    }
}

class Main {
    public static void main(String[] args) {
        int[] v = {7, 15, 6, 3};
        int h = 8;

        // Create an object of the Solution class
        Solution sol = new Solution();

        int ans = sol.minimumRateToEatBananas(v, h);

        // Print the result
        System.out.println("Koko should eat at least " + ans + " bananas/hr.");
    }
}
import math

class Solution:
    # Helper function to find the maximum element in the list 
    def findMax(self, v):
        maxi = float('-inf')
        n = len(v)
        
        # Find the maximum element
        for i in range(n):
            maxi = max(maxi, v[i])
        return maxi

    """ Helper function to calculate total hours
        required at given hourly rate """
    def calculateTotalHours(self, v, hourly):
        totalH = 0
        n = len(v)
        
        # Calculate total hours required
        for i in range(n):
            totalH += math.ceil(v[i] / hourly)
        return totalH

    # Function to find the minimum rate to eat bananas 
    def minimumRateToEatBananas(self, nums, h):
        # Find the maximum number of bananas
        maxi = self.findMax(nums)

        """ Find the minimum value of k
            that satisfies the condition """
        for i in range(1, maxi + 1):
            reqTime = self.calculateTotalHours(nums, i)
            if reqTime <= h:
                return i

        """ Dummy return statement (should 
            not be reached in valid cases) """
        return maxi

# Driver Code
if __name__ == "__main__":
    v = [7, 15, 6, 3]
    h = 8

    # Create an object of the Solution class
    sol = Solution()

    ans = sol.minimumRateToEatBananas(v, h)

    # Print the result
    print(f"Koko should eat at least {ans} bananas/hr.")
class Solution {
    // Helper function to find the maximum element in the array
    findMax(v) {
        let maxi = Number.MIN_SAFE_INTEGER;
        let n = v.length;

        // Find the maximum element
        for (let i = 0; i < n; i++) {
            maxi = Math.max(maxi, v[i]);
        }
        return maxi;
    }

    /* Helper function to calculate total hours
       required at given hourly rate */
    calculateTotalHours(v, hourly) {
        let totalH = 0;
        let n = v.length;

        // Calculate total hours required
        for (let i = 0; i < n; i++) {
            totalH += Math.ceil(v[i] / hourly);
        }
        return totalH;
    }

    // Function to find the minimum rate to eat bananas
    minimumRateToEatBananas(nums, h) {
        // Find the maximum number of bananas
        let maxi = this.findMax(nums);

        /* Find the minimum value of k
           that satisfies the condition */
        for (let i = 1; i <= maxi; i++) {
            let reqTime = this.calculateTotalHours(nums, i);
            if (reqTime <= h) {
                return i;
            }
        }

        /* Dummy return statement (should 
           not be reached in valid cases) */
        return maxi;
    }
}

// Driver Code
const v = [7, 15, 6, 3];
const h = 8;

// Create an object of the Solution class
const sol = new Solution();

const ans = sol.minimumRateToEatBananas(v, h);

// Print the result
console.log(`Koko should eat at least ${ans} bananas/hr.`);

Complexity Analysis:

Time Complexity:O(max * N), where max is the maximum element in the array and N is the size of the array. We are running nested loops. The outer loop runs for max times in the worst case and the inner loop runs for N times.

Space Complexity: As no additional space is used, so the Space Complexity is O(1).

Intuition:

The idea here is to use binary search algorithm to solve this problem in a optimized way. Now, the search space will be in the range[1,max], where max is the maximum element in the array because the maximum bananas that the monkey can it per our can be the maximum element of the array. As, the search space is sorted so binary search can be applied for better time complexity.

Approach:

Working of minimumRateToEatBananas(nums, h):

Starts by initializing low to 1 (minimum possible eating rate) and high to maximum element of the array using findMax function, which finds the maximum element in the given array. This sets up the binary search bounds where the eating rate will be searched.
Initialize a while loop that continues as long as low is less than or equal to high. Compute mid as the midpoint between low and high.
Use the function calculateTotalHours to estimate how many hours would be needed to eat all bananas in the array at the rate `mid` bananas per hour.
Compare total hour (total hours calculated at rate mid) with h (desired total hours), If total hour is less than or equal to h, it means the current eating rate mid is sufficient or possibly too high, so adjust high to mid - 1 to search for potentially smaller rates. Else, adjust low to mid + 1 to search for higher rates that might still satisfy the condition.
Once the binary search completes (low > high), low represents the minimum eating rate such that eating all bananas within h hours is feasible.

Working of findMax(arr):

First initialize a variable 'maxi', which will store maximum element of the array.
Now, literate through the array and find the maximum element among them, and return it.

Working of calculateTotalHours(arr,hourly):

Start with initializing n = size of array, which gives the number of elements in the array. Initialize 'totalH' to 0, which will accumulate the total hours required. 'hourly' represents the number of items that can be processed per hour.
Compute the number of hours required to eat all bananas at the rate of 'hourly' bananas per hour and store in 'totalH'. Use ceil function to round up the division result to ensure that partial hours are counted correctly when necessary. Ater the traversal has ended, return 'totalH' as answer.

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

class Solution {
private:
    /* Helper function to find the
    maximum element in the vector */
    int findMax(vector<int>& nums) {
        int maxi = INT_MIN;
        int n = nums.size();
        
        // Find the maximum element
        for (int i = 0; i < n; i++) {
            maxi = max(maxi, nums[i]);
        }
        return maxi;
    }

    /* Helper function to calculate total 
    hours required at given hourly rate */
    int calculateTotalHours(vector<int>& nums, int hourly) {
        int totalH = 0;
        int n = nums.size();
        
        // Calculate total hours required
        for (int i = 0; i < n; i++) {
            totalH += ceil((double) nums[i] / (double) hourly);
        }
        return totalH;
    }

public:
    /* Function to find the 
    minimum rate to eat bananas */
    int minimumRateToEatBananas(vector<int>& nums, int h) {
        // Initialize binary search bounds
        int low = 1, high = findMax(nums);

        // Apply binary search
        while (low <= high) {
            int mid = (low + high) / 2;
            int totalH = calculateTotalHours(nums, mid);
            if (totalH <= h) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
};

int main() {
    vector<int> nums = {7, 15, 6, 3};
    int h = 8;

    // Create an object of the Solution class
    Solution sol;

    int ans = sol.minimumRateToEatBananas(nums, h);

    // Print the result
    cout << "Koko should eat at least " << ans << " bananas/hr.\n";

    return 0;
}
import java.util.*;

class Solution {
    /* Helper function to find the
    maximum element in the array*/
    private int findMax(int[] nums) {
        int maxi = Integer.MIN_VALUE;
        int n = nums.length;

        // Find the maximum element
        for (int i = 0; i < n; i++) {
            maxi = Math.max(maxi, nums[i]);
        }
        return maxi;
    }

    /* Helper function to calculate total
    hours required at given hourly rate*/
    private int calculateTotalHours(int[] nums, int hourly) {
        int totalH = 0;
        int n = nums.length;

        // Calculate total hours required
        for (int i = 0; i < n; i++) {
            totalH += Math.ceil((double) nums[i] / (double) hourly);
        }
        return totalH;
    }

    /* Function to find the 
    minimum rate to eat bananas*/
    public int minimumRateToEatBananas(int[] nums, int h) {
        // Initialize binary search bounds
        int low = 1, high = findMax(nums);

        // Apply binary search
        while (low <= high) {
            int mid = (low + high) / 2;
            int totalH = calculateTotalHours(nums, mid);
            if (totalH <= h) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {7, 15, 6, 3};
        int h = 8;

        // Create an object of the Solution class
        Solution sol = new Solution();

        int ans = sol.minimumRateToEatBananas(nums, h);

        // Print the result
        System.out.println("Koko should eat at least " + ans + " bananas/hr.");
    }
}
import math

class Solution:
    """ Helper function to find the
    maximum element in the array"""
    def findMax(self, nums):
        maxi = float('-inf')
        n = len(nums)

        # Find the maximum element
        for i in range(n):
            maxi = max(maxi, nums[i])
        return maxi

    """ Function to calculate total hours
    required at given hourly rate"""
    def calculateTotalHours(self, nums, hourly):
        totalH = 0
        n = len(nums)

        # Calculate total hours required
        for i in range(n):
            totalH += math.ceil(nums[i] / hourly)
        return totalH

    """ Function to find the 
    minimum rate to eat bananas"""
    def minimumRateToEatBananas(self, nums, h):
        # Initialize binary search bounds
        low, high = 1, self.findMax(nums)

        # Apply binary search
        while low <= high:
            mid = (low + high) // 2
            totalH = self.calculateTotalHours(nums, mid)
            if totalH <= h:
                high = mid - 1
            else:
                low = mid + 1
        return low

if __name__ == "__main__":
    nums = [7, 15, 6, 3]
    h = 8

    # Create an object of the Solution class
    sol = Solution()

    ans = sol.minimumRateToEatBananas(nums, h)

    # Print the result
    print(f"Koko should eat at least {ans} bananas/hr.")
class Solution {
    /* Helper function to find the
    maximum element in the array */
    findMax(nums) {
        let maxi = Number.MIN_SAFE_INTEGER;
        const n = nums.length;

        // Find the maximum element
        for (let i = 0; i < n; i++) {
            maxi = Math.max(maxi, nums[i]);
        }
        return maxi;
    }

    /*Helper function to calculate total 
    hours required at given hourly rate*/
    calculateTotalHours(nums, hourly) {
        let totalH = 0;
        const n = nums.length;

        // Calculate total hours required
        for (let i = 0; i < n; i++) {
            totalH += Math.ceil(nums[i] / hourly);
        }
        return totalH;
    }

    /* Function to find the 
    minimum rate to eat bananas*/
    minimumRateToEatBananas(nums, h) {
        // Initialize binary search bounds
        let low = 1, high = this.findMax(nums);

        // Apply binary search
        while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            const totalH = this.calculateTotalHours(nums, mid);
            if (totalH <= h) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

const nums = [7, 15, 6, 3];
const h = 8;

//Create an instance of Solution class
const sol = new Solution();

const ans = sol.minimumRateToEatBananas(nums, h);

// Print the result
console.log(`Koko should eat at least ${ans} bananas/hr.`);

Complexity Analysis:

Time Complexity:O(N * log(max)), where max is the maximum element in the array and N is size of the array. We are applying Binary search for the range [1, max], and for every value of ‘mid’, we are traversing the entire array inside the function named calculateTotalHours().

Space Complexity: As no additional space is used, so the Space Complexity is O(1).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Complexity Analysis:

Intuition:

Approach:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code