# 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 plant 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: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB