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

# 🚀 _5. Koko Eating Bananas_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/searching-bonus-problems/problem/koko-eating-bananas)

## 💡 **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++)

```cpp
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)

```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)

```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](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

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

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>