Show problems as
Classic problem #2226MediumArrayBinary Search

Maximum Candies Allocated to K Children

Real-world version: Longest Lead Cut From The Reels
Tracked in this browser only
Read Maximum Candies Allocated to K Children on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A depot holds cable on reels, reels[i] being the whole number of metres left on reel i. An order calls for leads service leads, and every lead must be cut to the same whole number of metres.

A reel can be cut into as many leads as fit, and whatever is left over on it is scrap. A lead is one continuous run of cable, so it must come from a single reel: two short offcuts cannot be joined into one lead. Making more leads than the order asks for is fine, and reels may be left untouched.

Return the greatest length, in whole metres, that lets the order be filled. Return 0 when the depot cannot fill it even with one-metre leads.

Examples

Example 1

Input
reels = [16, 9, 27], leads = 7
Output
6

At 6 metres the reels give 2, 1 and 4 leads, which is the 7 the order asks for. At 7 metres they give only 6.

Example 2

Input
reels = [4], leads = 5
Output
0

The single reel holds 4 metres, so even one-metre leads come to 4, one short of the order.

Example 3

Input
reels = [100, 100], leads = 4
Output
50

Each reel gives two 50-metre leads, filling the order of 4 exactly.

Constraints

  • 1 <= reels.length <= 10^5
  • 1 <= reels[i] <= 10^7
  • 1 <= leads <= 10^12

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_lead(reels: list[int], leads: int) -> int:
Java
public int longestLead(int[] reels, long leads)

More on the same topics