5. Koko Eating Bananas.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	Binary Search Arrays

🚀 5. Koko Eating Bananas 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description

Koko is given an array arr[] of integers where each element represents a pile of bananas. Koko has k hours to finish all the piles. The task is to find the minimum number of bananas s that Koko must eat per hour in order to finish all the piles within k hours.

Each hour, Koko selects a pile and eats s bananas from it. If the pile contains fewer than s bananas, she consumes the entire pile for that hour. Koko cannot eat more than s bananas per hour.

We need to find the smallest integer s such that Koko finishes all piles within k hours.

🔍 Example Walkthrough

Input:

arr[] = [3, 6, 7, 11], k = 8

Output:

4

Explanation:
Koko can finish all the piles within 8 hours by eating 4 bananas per hour:

• First pile (3 bananas): Takes 1 hour.
• Second pile (6 bananas): Takes 2 hours.
• Third pile (7 bananas): Takes 2 hours.
• Fourth pile (11 bananas): Takes 3 hours.

Total: 1 + 2 + 2 + 3 = 8 hours.

Input:

arr[] = [30, 11, 23, 4, 20], k = 5

Output:

30

Explanation:
With 30 bananas per hour, Koko can finish each pile in 1 hour:

• Pile 1 (30 bananas): 1 hour.
• Pile 2 (11 bananas): 1 hour.
• Pile 3 (23 bananas): 1 hour.
• Pile 4 (4 bananas): 1 hour.
• Pile 5 (20 bananas): 1 hour.

Total: 5 hours (which is exactly k = 5).

Input:

arr[] = [5, 10, 15, 20], k = 7

Output:

10

Explanation:
At 10 bananas per hour, Koko finishes in 7 hours:

• First pile (5 bananas): 1 hour.
• Second pile (10 bananas): 1 hour.
• Third pile (15 bananas): 2 hours.
• Fourth pile (20 bananas): 2 hours.

Total: 1 + 1 + 2 + 2 = 7 hours.

Constraints:

• $1 <= arr.size() <= 10^5$
• $1 <= arr[i] <= 10^4$
• $arr.size() <= k <= 2*10^5$

🎯 My Approach

Step-by-Step Approach:

1. Initial Setup:
   The minimum number of bananas Koko could eat per hour is 1 and the maximum is the largest pile in the array (since she can eat all bananas from the largest pile in 1 hour). We will use binary search to find the smallest s in this range.

2. Binary Search Logic:

   • Calculate the middle point mid between the current low (l) and high (h) values.
   • Calculate the total number of hours Koko would need to eat all piles at a rate of mid bananas per hour.
   • If the total hours are less than or equal to k, then mid is a potential answer, and we attempt to reduce s by searching the left half (h = mid).
   • If the total hours exceed k, then mid is too small, and we need to increase s by searching the right half (l = mid + 1).
   • The search stops when l equals h.

3. Final Result:
   The value of l (or h, since they will converge) will be the minimum number of bananas Koko must eat per hour.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n * log(max(arr))), where n is the size of the array and max(arr) is the largest pile.
  The binary search runs in O(log(max(arr))) iterations, and for each iteration, we sum the hours for all piles, which takes O(n) time.

• Expected Auxiliary Space Complexity: O(1), as we are using a constant amount of space beyond the input array.

📝 Solution Code

Code (C++)

class Solution {
public:
    int kokoEat(vector<int>& arr, int k) {
        int l = 1, h = *max_element(arr.begin(), arr.end());
        while (l < h) {
            int mid = l + (h - l) / 2, sum = 0;
            for (int p : arr) sum += (p + mid - 1) / mid;
            if (sum <= k) h = mid;
            else l = mid + 1;
        }
        return l;
    }
};

Code (Java)

class Solution {
    public static int kokoEat(int[] arr, int k) {
        int l = 1, h = Arrays.stream(arr).max().getAsInt();
        while (l < h) {
            int mid = l + (h - l) / 2;
            int sum = 0;
            for (int p : arr) sum += (p + mid - 1) / mid;
            if (sum <= k) h = mid;
            else l = mid + 1;
        }
        return l;
    }
}

Code (Python)

class Solution:
    def kokoEat(self, arr, k):
        l, h = 1, max(arr)
        while l < h:
            mid = l + (h - l) // 2
            sum_parts = sum((p + mid - 1) // mid for p in arr)
            if sum_parts <= k:
                h = mid
            else:
                l = mid + 1
        return l

📢 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count