Skip to content
Katabench
Try free

Magnetic Force Between Two Balls

Hard About 35 min Free, no account needed

Place m balls in baskets to maximize the smallest gap between any two.

The brief

Baskets sit at positions[i] (distinct). Place m balls into baskets so that the minimum distance between any two balls is as large as possible, and return that distance.

The performance bar

The obvious approach tries minimum-gap 1, 2, 3, ... placing balls until a gap fails. The hidden test's best gap is nearly 100,000, with an O(n) placement check per candidate, so the linear walk over gaps is far too slow. Note that if m balls fit with gap g, they also fit with any smaller gap, which lets you narrow the range of g far faster than one step at a time.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the largest achievable minimum distance between any two of the m balls.
    public int MaxForce(int[] positions, int m)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Binary search on the answer
Search the space of candidate answers when feasibility is monotonic.
Greedy algorithms
Make the locally best choice when an exchange argument proves it stays globally optimal.

Do these first

Related katas