24. Aggressive Cows

//{ Driver Code Starts
// Initial function template for C++

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


// } Driver Code Ends
// User function Template for C++

class Solution {
  public:
    bool Canweplace(vector<int> &a, int d, int cows, int size)
    {
        int count = 1, prev = a[0];       //one cow is already placed so count = 1
        for(int i = 1; i < size; i++)
        {
            if(a[i] - prev >= d)
            {
                count++;
                prev = a[i];
            }
            if(count >= cows)
            {
                return true;
            }
        }
        return false;
    }
    int aggressiveCows(vector<int> &stalls, int k) {

        // Write your code here
        sort(stalls.begin(), stalls.end());
        int n = stalls.size();
        int ans = 0;
        int lo = 1, hi = stalls[n - 1] - stalls[0];
        while(lo <= hi)
        {
            int mid = (lo + hi) / 2;
            if(Canweplace(stalls, mid, k, n) == true)
            {
                ans = mid; 
                lo = mid + 1;
            }
            else
            {
                hi = mid - 1;
            }
        }
        return ans;
    }
};

//{ Driver Code Starts.

int main() {
    int test_case;
    cin >> test_case;
    cin.ignore();
    while (test_case--) {

        int k;
        vector<int> arr;
        string input;
        getline(cin, input);
        stringstream ss(input);
        int number;
        while (ss >> number) {
            arr.push_back(number);
        }
        string in;
        getline(cin, in);
        stringstream sss(in);
        int num;
        while (sss >> num) {
            k = num;
        }
        Solution ob;
        int ans = ob.aggressiveCows(arr, k);
        cout << ans << endl;
        cout << "~" << endl;
    }
    return 0;
}

// } Driver Code Ends