Aggressive Cows
Binary Search on Answers DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Aggressive Cows Problem: Maximizing Minimum Distance Between K Cows Placed in Stalls, Arrays, Sorting, Binary Search, Brute Force, Time Complexity, Space Complexity, Big O Notation, Loops, Conditional Statements, brute force, greedy algorithm, sorting algorithms, binary search, time complexity analysis, Greedy Strategies.
Aggressive Cows Problem Statement You are given an array arr of size n which denotes the positions of stalls. You are also given an integer k which denotes the number of aggressive cows. Your task is to assign stalls to k cows such that the minimum distance between any two of them is the maximum possible. Find the maximum possible minimum distance. Each stall can accommodate only one cow. Input Specification The first line contains an integer N, the number of stalls. The second line contains an integer k, the number of aggressive cows. The third line contains N space separated integers representing the stall positions arr[i]. Output Specification Print a single integer representing the maximum possible minimum distance. Constraints 2 <= N <= 10^5 2 <= k <= N 0 <= arr[i] <= 10^9 All arr[i] are distinct. Sample Test Cases Sample Input 1: Sample Output 1: Explanation 1: The maximum possible minimum distance between any two cows will be 3 when 4 cows are placed at positions {0, 3, 7, 10}. Here the distances between cows are 3, 4, and 3 respectively. We cannot make the minimum distance greater than 3 in any way. Sample Input 2: Sample Output 2: Explanation 2: The maximum possible minimum distance between any two cows will be 5 when 2 cows are placed at positions {1, 6}.