Home/Questions/Q 3520
Next
In Process

RTSALL Latest Articles

Abhishek
Begginer
Asked: 2026-09-11T09:51:19-05:00 In: ,

Binary Search on Answer: How to solve Koko Eating Bananas without floating-point bugs?

I’m trying to master the pattern known as Binary Search on the Answer Space. In problems like Koko Eating Bananas (or Ship Packages within D Days), we search for a minimum speed k that satisfies a time limit h.

However, when calculating ceiling hours like ceil(pile / k), many developers run into subtle floating-point precision issues or off-by-one boundary bugs where low and high get stuck in infinite loops. What is the bulletproof mathematical pattern to solve this cleanly?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhishek
    Begginer

    In C++, when solving Koko Eating Bananas (or Ship Packages within D Days), you must avoid floating-point math and use int64_t for accumulating hours to prevent integer overflow bugs.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

int minEatingSpeed(const std::vector<int>& piles, int h) {
    int low = 1;
    int high = *std::max_element(piles.begin(), piles.end());
    int ans = high;

    auto canFinish = [&](int speed) -> bool {
        int64_t total_hours = 0;
        for (int pile : piles) {
            // Integer ceiling trick: (pile + speed - 1) / speed
            total_hours += (static_cast<int64_t>(pile) + speed - 1) / speed;
            if (total_hours > h) return false; // Early exit
        }
        return total_hours <= h;
    };

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canFinish(mid)) {
            ans = mid;
            high = mid - 1; // Try slower speed
        } else {
            low = mid + 1;  // Must eat faster
        }
    }
    return ans;
}

int main() {
    std::vector<int> piles = {3, 6, 7, 11};
    int h = 8;
    std::cout << "Minimum Eating Speed: " << minEatingSpeed(piles, h) << " bananas/hourn";
    return 0;
}

    Complexity: Runs in O(N log(max_pile)) time with O(1) space. Zero floating-point roundoff issues.

    • 0
  2. Abhay Tiwari
    Begginer

    Binary Search on Answer Space is one of the highest-leverage algorithmic patterns you can learn. Once you recognize it, dozens of seemingly hard problems (shipping packages, splitting arrays, cutting ribbons, allocating memory) all collapse into the exact same 15 lines of code.

    1. When Can You Use This Pattern?

    Ask yourself one simple question: Is the condition monotonic?

    • If Koko eats at speed k = 100 bananas/hour and succeeds in finishing in under h hours, would eating at speed k = 101 also succeed? Yes, always.
    • If eating at speed k = 5 is too slow and fails, would eating at speed k = 4 also fail? Yes, always.

    Because the outcome transitions cleanly from False, False, ..., True, True, True, the answer space is monotonic. That means we don’t need to test every speed from 1 to 1 billion linearly—we can binary search it in O(log(MaxPile)) steps!

    2. The Integer Ceiling Trick (Say Goodbye to Float Bugs)

    If Koko has a pile of 7 bananas and eats at speed k = 3, she needs ceil(7 / 3) = 3 hours.

    In Python or C++, doing math.ceil(pile / k) converts the numbers to IEEE-754 64-bit floats. On massive numbers (e.g. 10^14), floating-point precision degrades, causing silent off-by-one errors.

    The standard integer arithmetic replacement for ceil(a / b) is:

    hours = (pile + k - 1) // k

    Let’s test it: (7 + 3 - 1) // 3 = 9 // 3 = 3. Exactly right, 100% integer math, zero float conversions!

    3. Clean Python 3.12 Implementation

    from typing import Sequence

def min_eating_speed(piles: Sequence[int], h: int) -> int:
    """Finds minimum integer eating speed k such that total hours <= h."""
    
    # Lower bound: Koko must eat at least 1 banana per hour
    # Upper bound: Eating faster than the largest pile doesn't save any more time
    low = 1
    high = max(piles)
    ans = high

    def can_finish(speed: int) -> bool:
        total_hours = 0
        for pile in piles:
            # Equivalent to ceil(pile / speed) without floats
            total_hours += (pile + speed - 1) // speed
            if total_hours > h:
                return False  # Early exit optimization
        return total_hours <= h

    while low <= high:
        mid = low + (high - low) // 2
        
        if can_finish(mid):
            ans = mid         # mid is valid, but can we go even slower?
            high = mid - 1    # try searching left
        else:
            low = mid + 1     # too slow, must eat faster

    return ans

    4. Complexity & Production Benchmarks

    • Time Complexity: O(N * log(M)) where N is the number of piles and M is max(piles). If M = 10^9, log2(10^9) ≈ 30. Even with 100,000 piles, the validation function runs at most 30 times. Total operations: ~3 million, executing in under 15 milliseconds.
    • Space Complexity: O(1) auxiliary memory.
    • Overflow Note for C++ / Java: In C++, total_hours can easily exceed 2^31 - 1 if speeds are small and piles are large. Always declare int64_t total_hours = 0; to prevent integer overflow.
    • 0