BS-12. Koko Eating Bananas

Solving the “Koko Eating Bananas” Problem Using Binary Search

The video explains how to solve the “Koko Eating Bananas” problem by using binary search to find the minimum integer eating speed (bananas per hour) that allows Koko to finish eating all banana piles within a given deadline (hours).

---

Key Concepts and Steps

Problem Setup

• Given n piles of bananas, each with a certain number of bananas.
• Koko must eat all bananas within H hours.
• Koko can only eat from one pile at a time and cannot move to the next pile until the current one is finished.
• Eating speed K (bananas per hour) must be an integer.
• Goal: Find the minimum K such that Koko finishes within H hours.

Understanding the Eating Time Calculation

• For each pile, time taken = ceiling of (bananas in pile / K).
• Sum the times for all piles to get total hours.
• Example:
  • Piles: [3, 6, 7, 11], H = 8 hours.
  • Trying K = 2 bananas/hour results in 15 hours (too slow).
  • Trying K = 4 bananas/hour results in exactly 8 hours (meets deadline).

Naive Approach (Linear Search)

• Start from K = 1 and increment until total hours ≤ H.
• Time complexity: O(max(pile) * n), which can be inefficient for large inputs.

Optimized Approach (Binary Search)

• Set minimum speed low = 1.
• Set maximum speed high = max number of bananas in any pile.
• Use binary search between low and high to find the minimum feasible K.
• For each mid value (candidate K), calculate total hours.
• If total hours ≤ H, try to find a smaller K by moving high to mid - 1.
• Else, move low to mid + 1.
• Continue until low exceeds high.
• The answer is the lowest K for which total hours ≤ H.

Binary Search Time Complexity

• O(n * log(max(pile)))

Important Implementation Details

• Use ceiling division carefully by converting operands to double before division to avoid integer division truncation.
• Write helper functions:
  • To find the maximum pile size.
  • To calculate total hours for a given K.

---

Summary of the Binary Search Algorithm

1. Initialize low = 1, high = max(piles).
2. While low <= high:
   • Calculate mid = (low + high) // 2.
   • Compute total hours needed at speed mid.
   • If total hours ≤ H, update answer to mid and set high = mid - 1.
   • Else, set low = mid + 1.
3. Return the answer.

---

Notable Points

• The problem is part of the Strivers A to Z DSA course.
• Code examples and problem links are provided in multiple languages: C++, Java, Python, JavaScript.
• The video emphasizes the importance of choosing the correct range for binary search to optimize performance.
• The speaker encourages viewers to subscribe and follow on social media.

---

Additional Information

• Problem: “Koko Eating Bananas” (a common binary search problem).
• Course: Strivers A to Z DSA course.
• Platforms: YouTube channel hosting the tutorial.
• Languages Covered: C++, Java, Python, JavaScript.
• Speaker: Unnamed instructor guiding through the problem solution.