(7) Binary Search: Workout

Question Link

Difficulty: Hard

Problem Statement: Given an array, you need to minimize the maximum difference between two adjacent elements.

Approach: In the ok function mid is minimized maximum value which we want to put between two adjacent arrays. If the total we got by doing this is less than k then high = mid;.

#include <bits/stdc++.h>
using namespace std;

bool ok(vector<int> arr, int mid, int k)
{
    int n = arr.size(), total = 0;
    for (int i = 1; i < n; i++)
    {
        total += (arr[i] - arr[i - 1] - 1) / mid;
    }
    return total <= k;
}
int solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    int low = 1, high = 1e9, mid;
    while (low < high)
    {
        mid = low + (high - low) / 2;
        if (ok(arr, mid, k)) high = mid;
        else low = mid + 1;
    }
    return low;
}
signed main()
{
    int tt, p = 1;
    cin >> tt;
    while (tt--)
    {
        cout << "Case #" << p << ": ";
        cout << solve() << endl;
        p++;
    }
}

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