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 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
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.
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
- Ship Packages Within D Days Medium Free Smallest ship capacity that delivers the conveyor belt on schedule.
- Fewest Cache Fetches Hard Free Use tomorrow's requests to find the smallest possible number of cache misses today.
- Text Justification Hard Free Greedily pack words into fully justified lines, spaces and all.
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.