(9) Binary Search: Minimum Speed to Arrive on Time

Question Link and Solution Link

Difficulty: Medium

Problem Statement: Given distance array and hour. Hour determines how many hours we need to complete the distance. We need to calculate the minimum speed such that we can complete the journey in a given hour. Also every time we need to take an integer value.

Approach: We traverse through the array and the total variable maintains the total time taken. Every time we take ceil value of total by snippet if (total > (int)total) total = (double)((int)total + 1);

bool ok(vector<int> &dist, double hour, int mid)
{
    double total = 0;
    for (int i : dist)
    {
        if (total > (int)total) total = (double)((int)total + 1);
        total += (double)i / (double)mid;
    }
    return total <= hour;
}
int minSpeedOnTime(vector<int> &dist, double hour)
{
    int low = 1, high = 1e7 + 9, mid;
    while (low < high)
    {
        mid = low + (high - low) / 2;
        if (ok(dist, hour, mid)) high = mid;
        else low = mid + 1;
    }
    return (low > 10000000 ? -1 : low);
}

Subscribe to the newsletter so that you never miss any post or update just like this one.

You can follow me on Hashnode for:

• Daily Data Structure and Algorithm based questions

• Getting knowledge of various development-related tools, concepts, and practices

  Twitter , GitHub , LinkedIn and Hashnode