Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Binary Search

Aggressive Cows

Hard · Binary Search · Asked at Amazon, Google, Flipkart, Directi

There are n stalls at given positions. Place c cows in different stalls so that the minimum distance between any two cows is as large as possible. Print that largest minimum distance.

Input

First line: n c. Second line: n stall positions.

Output

The largest possible minimum distance.

Constraints

Sort the stalls, binary search on the distance and place cows greedily.

Example 1

Input

5 3
1 2 8 4 9

Output

3

Example 2

Input

3 2
10 1 2

Output

9

Hints

  1. If cows can be placed with minimum gap d, they can also be placed with any smaller gap.
  2. Sort the stalls. For a fixed d, place cows greedily: first stall, then every next stall at least d away. Binary search the largest d that fits c cows.

Approach

After sorting, canPlace(d) puts a cow in the first stall and then in each stall at least d past the last cow. Taking the earliest possible stall each time is optimal, because it leaves the most room for the rest. canPlace is true up to some value and false beyond it, so binary search d between 1 and last − first for the largest feasible value.

Complexity: O(n log n + n log(range)) time · O(1) extra space

Solution

C++ solution

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

int main() {
    int n, c;
    cin >> n >> c;
    vector<long long> s(n);
    for (auto &x : s) cin >> x;
    sort(s.begin(), s.end());
    auto canPlace = [&](long long d) {
        int cows = 1;
        long long last = s[0];
        for (int i = 1; i < n; i++)
            if (s[i] - last >= d) {
                cows++;
                last = s[i];
            }
        return cows >= c;
    };
    long long lo = 1, hi = s[n - 1] - s[0];
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (canPlace(mid)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, c = data[0], data[1]
s = sorted(data[2 : 2 + n])


def can_place(d):
    cows, last = 1, s[0]
    for x in s[1:]:
        if x - last >= d:
            cows += 1
            last = x
            if cows >= c:
                return True
    return cows >= c


lo, hi = 1, s[-1] - s[0]
while lo < hi:
    mid = (lo + hi + 1) // 2
    if can_place(mid):
        lo = mid
    else:
        hi = mid - 1
print(lo)

Java solution

import java.util.*;

public class Main {
    static long[] s;
    static int c;

    static boolean canPlace(long d) {
        int cows = 1;
        long last = s[0];
        for (int i = 1; i < s.length; i++)
            if (s[i] - last >= d) {
                cows++;
                last = s[i];
            }
        return cows >= c;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        c = sc.nextInt();
        s = new long[n];
        for (int i = 0; i < n; i++) s[i] = sc.nextLong();
        Arrays.sort(s);
        long lo = 1, hi = s[n - 1] - s[0];
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2;
            if (canPlace(mid)) lo = mid;
            else hi = mid - 1;
        }
        System.out.println(lo);
    }
}

Solve Aggressive Cows online · All practice problems