Koko eating bananas

Looking at binary search thru different lens

Problem statement

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Koko has to complete eating all the bananas in n piles before h hours.

Lets think about naive solution first.

We can iterate from 1 to MAX and for each number check if koko can finish eating all the bananas with h hours. It will be minimum as we start from min value (1) and increment and check. This takes $O(n*$ MAX $)$ time. n for checking if $i$ is minimum and MAX for iterating 1 $\rightarrow$ MAX.

We can reduce this further. See how we are iterating from 1 $\rightarrow$ MAX. We can instead do lower bound search to find min k. Lets see how we can achieve this.

Lets define counting logic first.

private fun calculateCount(piles: IntArray, k: Int): Int{
    var count = 0
    piles.forEach{
        count += (it/k)
        if(it%k != 0){
            count++
        }
    }
    return count
}

Now lower bound search for number that satisfies above condition.

private fun lowerBoundSearch(piles: IntArray, maxValue: Int, h: Int): Int{
    // Reducing i by 1 and increasing j by 1 is a neat trick to avoid same mid.
    // Using this trick you can assign mid to i or j instead of mid + 1 or mid - 1
    var i = 0 // Reduce by 1. Here search starts from 1. Reduce by 1 to 0
    var j = maxValue+1
    var mid = 0

    while((i+1)<j){
        mid = (i+j).ushr(1)
        if(calculateCount(piles, mid) <= h) j = mid
        else i = mid
    }

    return j
}

Now just find the MAX value and do lower bound search.

fun minEatingSpeed(piles: IntArray, h: Int): Int {
    var maxValue = 0
    piles.forEach{
        maxValue = maxOf(it, maxValue)
    }

    return binarySearch(piles, maxValue, h)
}

Time complexity for this approach is $O(n*log($ MAX $))$

Full code

Solution.kt

fun minEatingSpeed(piles: IntArray, h: Int): Int {
    var maxValue = 0
    piles.forEach{
        maxValue = maxOf(it, maxValue)
    }

    return binarySearch(piles, maxValue, h)
}

private fun lowerBoundSearch(piles: IntArray, maxValue: Int, h: Int): Int{
    // Reducing i by 1 and increasing j by 1 is a neat trick to avoid same mid.
    // Using this trick you can assign mid to i or j instead of mid + 1 or mid - 1
    var i = 0 // Reduce by 1. Here search starts from 1. Reduce by 1 to 0
    var j = maxValue+1
    var mid = 0

    while((i+1)<j){
        mid = (i+j).ushr(1)
        if(calculateCount(piles, mid) <= h) j = mid
        else i = mid
    }

    return j
}

private fun calculateCount(piles: IntArray, k: Int): Int{
    var count = 0
    piles.forEach{
        count += (it/k)
        if(it%k != 0){
            count++
        }
    }
    return count
}

Checkout my solutions for other coding questions.