League Training Boosts
Minimum days to meet array targets with uniform gains and one bonus per day
A football league is preparing its clubs for a new season. Club i needs at least needs[i] training credits before it is ready.
Every training day gives every club base credits. In addition, the league may choose at most one club that day to receive bonus extra credits. The same club may receive the extra credits on multiple days. Credits beyond a club's requirement are harmless.
All clubs start with zero credits. Return the minimum number of whole training days needed to make every club ready. If every requirement is already zero, return 0.
Examples
Example 1
Input: needs = [8,5,3], base = 2, bonus = 3 Output: 3
For requirements 8, 5, and 3, two days give each club 4 baseline credits. The first club would still need two boosts and the second would need one, exceeding the two available boosts. Three days suffice by boosting the first club once.
Example 2
Input: needs = [5,2], base = 0, bonus = 3 Output: 3
With no baseline credits, the clubs must receive their credits through individual boosts. The first club needs two boosts and the second needs one, so the boosts occupy three separate days.
Example 3
Input: needs = [0,0], base = 4, bonus = 2 Output: 0
Both clubs are already ready, so no training days are necessary.
Constraints
- 1 <= needs.length <= 4000
- 0 <= needs[i] <= 1000000000
- 0 <= base <= 1000000000
- 1 <= bonus <= 1000000000
- The returned number may exceed a signed 32-bit integer, but is always exactly representable as a JavaScript Number.
The intended solution takes O(n log U) time and O(1) auxiliary space, where U is the sum of the boost-only day requirements. The brute checker scans candidate days on tiny instances and uses a bounded-search fallback for large numeric inputs.
Hints
Show hint 1Hint 1
After a proposed number of days, how many extra credits does each club still need beyond its baseline credits?
Show hint 2Hint 2
Convert each remaining requirement into a minimum number of boosts. Compare their sum with the number of days, then use the monotonicity of this check.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the feasibility check change if up to c distinct clubs could receive a boost each day?
- How could you return a compact schedule giving each club's total number of boosts without listing every day?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem