368. Candy Pile Split
At a school fair, candy is sold in piles, and piles[i] is the number of candies in the i-th pile. A teacher may split any pile into smaller sub-piles, but she cannot merge piles together, so every share has to come from a single pile.
She wants to give children children the same number of candies each, with each child receiving candies from only one pile and some candies left over if necessary. Return the largest number of candies each child can get. If it is not even possible to give every child one candy, return 0. The number of children can be as large as 10^12, so use 64-bit integers.
Example 1
- Input:
- piles = [7,9,4], children = 5
- Output:
- 3
- Explanation:
With 3 candies per child, the piles supply 2 + 3 + 1 = 6 shares, which is enough for 5 children; with 4 candies they supply 1 + 2 + 1 = 4, not enough. So the answer is 3.
Example 2
- Input:
- piles = [2,2], children = 5
- Output:
- 0
- Explanation:
Even one candy per child needs 5 candies but only 4 exist, so the answer is 0.
Constraints
1 ≤ piles.length ≤ 105
1 ≤ piles[i] ≤ 107
1 ≤ children ≤ 1012
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log M), where M is the largest pile
- Space
- O(1)