Binary Search the Answer - Sparsely Planting Trees

Given n spots where you can plant a tree, you’d like to plant them as sparsely as possible to make sure they don’t disrupt each other in several years. The coordinates of the spots are given as integers .

Your task is to find the minimum distance between t trees if you plant them as sparsely as possible.

Input

The first line of the input contains two integers n (1 ≤ n ≤ 100 000) the number of spots and t (2 ≤ t ≤ n) the number of trees that need to be planted.

The next line contains n space-separated distinct integers (0 ≤ ≤ ) the coordinates of spots where a tree can be planted.

Output

The program should print the minimum distance d between trees when planted as sparsely as possible.

Examples

Input	Output
5 3 1 2 8 4 9	3

Explanation

We can plant the trees as coordinates 1, 4, and 9 ⇒ the minimum distance is 4-1 = 3.

Tutorial

We can solve this challenge by performing a binary search on the answer (the minimum distance between trees) and checking on each iteration if it would be possible to plan trees with a given minimum distance. There are several important conditions that need to hold in order for the binary search on the answer to be possible:

We should be able to check if the given candidate answer satisfies the problem statement or not (in our case - we should be able to check for a given minimum distance d if we can plant the trees so that they are at least d units apart).

The checking function def check(x): should return True if it’s possible to satisfy the problem statement with a candidate answer x and False otherwise.

For increasing candidate answers (different values of x), the value of the checking function should be :

False False False True True (impossible for the first several numbers and then possible for larger ones). In this case, we’re looking for the first True (the smallest valid value).
True True True True False False (possible for small numbers and impossible for larger ones). In this case, we’re looking for the last True (the largest valid value).

In our case, we would like to plant the trees as sparsely as possible. So, we would like the minimum distance to be as large as possible. If it’s possible to plant trees with a minimum distance of x, then it’s definitely possible to plan them denser and get a smaller x. Therefore, in our case, the values of the checking function will be True True True True False False and we aim to find the last True in this list (the largest (most sparse) minimal distance between the planted trees).

A naive approach to solving this problem would be to sequentially iterate over the candidate answers d - 1, 2, 3, etc., and check if we can plant the trees with distances of at least d.

Try to implement this approach first before moving forward.

With a binary search on the answer, there are 2 components - the checking part, and the binary search part:

n, t = ...
x = sorted(x)

def check(d):
    """ Check if we can plant `t` trees at least `d` units apart """
    planted = 0               # We need to plant t trees (currently planted 0)
    prev = float('-inf')      # The coordinate of the previous tree
    for xi in x:
        if xi - prev >= d:    # If we can plant another tree at xi
            planted += 1
            prev = xi
    return planted >= t

With the checking function implemented, we can perform a binary search on the answer to find the most optimal value for the minimum distance if we would like to plant the trees as sparsely as possible:

l, r = 1, max(x)         # The answer is always in the range [l; r)
while r - l > 1:         # There is at least one element in between to consider
    mid = (l + r) // 2   # Take the middle index
    if check(mid):       # If it's possible with mid => l = mid
        l = mid
    else:                # Otherwise set r = mid
        r = mid

print(l)

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB