Free Binary search lessonsBinary search · Stage 2 · Search on the answer · Step 3

As far apart as possible

Find the largest minimum gap you can keep when placing items, by searching gaps and checking them greedily. About 15 minutes.

A check that fails the other way

Stalls stand at various positions along a road, and you must place k cows in distinct stalls so that the closest pair of cows is as far apart as possible. The answer is a distance.

A smaller gap is easy to satisfy, and a bigger one is harder. So the gaps that work are 1, 2, 3, and then stop working. You are looking for the last gap that works, which is the mirror image of the earlier searches.

Small gaps: work; big gaps fail.

Find: the last gap that works.

In code

stalls.sort()
def fits(gap):
    placed, last = 1, stalls[0]
    for s in stalls[1:]:
        if s - last >= gap:
            placed += 1
            last = s
    return placed >= k

Stalls at 1, 2, 4, 8, 9 and 3 cows. Tinted stalls hold a cow.

leftright

Place 3 cows. The gap is at least 1 and at most (9 − 1) ÷ 2 = 4. Try the middle, rounded up: 3.

Move 1 of 4

Keep mid when it works

Put the first cow in the first stall. Then walk along, placing the next cow at the first stall at least the gap away from the last one. If you place at least k cows, the gap fits.

When the middle gap fits, the answer is that gap or bigger, so set low to mid. When it doesn't, set high to one less. Because low moves up to mid, use a middle that rounds up. Otherwise low and high can stay one apart forever.

Fits: low becomes mid.

Round the middle up: or the loop never finishes.

In code

span = stalls[-1] - stalls[0]
low, high = 1, span // (k - 1)
while low < high:
    mid = (low + high + 1) // 2
    if fits(mid):
        low = mid
    else:
        high = mid - 1
return low

Quick check

A gap of 5 lets you place all k cows. What can you say about a gap of 3?

AIt works too, so the answer is at least 5
BIt might fail
CIt gives the same answer

Show the answer

It works too, so the answer is at least 5. A smaller gap is easier to keep, so anything that works for 5 works for 3.

Your problem

Spread the cows out

stalls[i] is the position of stall i along a road, in no particular order. Place k cows in different stalls so that the smallest distance between any two cows is as large as possible. Return that largest possible smallest distance. There are at least k stalls, and k is at least 2.

Example

stalls = [1, 2, 4, 8, 9], k = 3 → 3

2 ≤ k ≤ stalls ≤ 100,000 · 0 ≤ position ≤ 1,000,000,000 · all positions different

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.