Search code examples
arraysbinary-search

What is the use of sqrt() function in this binary search question?

I was solving the Cooking Ninjas problem on code studio, and I could not understand some steps of the solution [Image attached below]. Can anyone please help me to understand this step of the solution?

This question is based on arrays and can be solved using binary search. But the condition for shifting of the start and end is a little hard to digest.

I tried this question with this code:

bool isPossible(vector<int> &rank, int m, int mid){
    int sumTime = 0;
    int dishCount = 0;
    
    for(int i=0; i<rank.size(); i++){
        
        for(int j=1; j<=m; j++){
            sumTime += j*rank[i];
            if(sumTime <= mid){
                dishCount++;
            }
            if(dishCount == m){
                return true;
            }
        }
        sumTime = 0;
    }
    return false;
}

int minCookTime(vector<int> &rank, int m){

    int s = 0;
    int e = 0;
    
    for(int i=1; i<=m; i++){
        e += i*rank[rank.size()-1];
    }
    
    int mid = s+(e-s)/2;
    int ans = -1;
    
    while(s<=e){
        if(isPossible(rank, m, mid)){
            ans = mid;
            e = mid - 1;
        }
        else{
            s = mid + 1;
        }
        mid = s+(e-s)/2;
    }
    return ans;
}

Although this solution also works but I want to understand the approach mentioned in the solution (attached below).

Image of the Solution

2

Please help me with this.

Solution

  • Let's say the rank of a cook is r, and the amount of time he is given is t. We want to find out the number of dishes he can cook in time t (let's call the number of dishes k).

    So, from the question, we have the equation ->
    r + 2r + 3r + .... k*r <= t

    Using formula for sum of first k natural numbers, we have -> r * (k*(k+1)/2) <= t

    Simplifying the above equation, we get -> k2 + k - (2t/r) <= 0

    Using quadratic formula, we get the solution as ->

    k <= (-1 + sqrt(1 + 8*t/2r))/2

    We are only taking the + part from the quadratic formula rejecting the - because the number of dishes cooked will be positive.

    Hope this helps :)