Cutting Ribbons
Medium About 20 min Free, no account needed
The longest equal piece length that still yields k pieces.
The brief
You have ribbons of lengths ribbons[i] and must cut at least k pieces of
the same integer length (leftover material is discarded; a ribbon may also be
left uncut). Return the maximum possible piece length, or 0 if even
length 1 cannot produce k pieces.
The obvious approach tries piece length 1, 2, 3, ... and keeps the last that
worked. The hidden test's best length is one billion, so stepping through
every candidate length is far too slow. You need to home in on the largest
feasible length without testing each one in turn.
Starter code
using System;
public class Solution
{
// TODO: return the longest piece length yielding at least k equal pieces (0 if impossible).
public long MaxRibbonLength(long[] ribbons, long k)
{
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.
Related katas
- Koko Eating Bananas Medium Free The slowest eating speed that still finishes every pile in time.
- Minimum Days to Make Bouquets Medium Free Earliest day enough adjacent flowers have bloomed for all the bouquets.
- Ship Packages Within D Days Medium Free Smallest ship capacity that delivers the conveyor belt on schedule.
- Integer Square Root Easy Free Floor of the square root, found without floating point.