Largest Equal Candy Portion for Every Child
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You may divide each pile in `candies` into smaller piles, but cannot merge candies from different original piles. Give each of `k` children one portion containing the same number of candies. Leftovers and unused piles are allowed. Return the greatest number each child can receive, or zero if even one candy per child is impossible.
```cpp
class Solution {
public:
int maximumCandies(vector<int>& candies, long long k);
};
```
### Examples
**Example 1:**
```text
candies = [4,7], k = 3
Output: 3
Explanation: Portions of size 3 give one from 4 and two from 7; size 4 gives only two portions.
```
**Example 2:**
```text
candies = [1,2], k = 5
Output: 0
Explanation: Three candies cannot provide five positive portions.
```
### Constraints
- `1 <= candies.length <= 10^5`; `1 <= candies[i] <= 10^7`.
- `1 <= k <= 10^12`, passed as long long.
### Clarifying Questions
A child's portion cannot combine leftovers from separate source piles. Returning zero expresses lack of any positive feasible size.
```hint Inspect the structure
How many full portions of size x can one original pile supply?
```
### Reasoning checkpoints
- Keep each child's portion within one original pile and give all k children equal amounts.
- Prove that the reported portion size is achievable and that every larger size is impossible.
- Handle very large k and a zero answer without invalid arithmetic.
### Optional extensions
Why can total candies divided by k overestimate the answer?
Overview: Largest Equal Candy Portion for Every Child. Split each original candy pile into smaller piles as desired, but never merge different original piles. Give each of k children exactly one equal-sized portion, leaving unused candies or piles if needed. Return the largest possible portion size, or zero if even one candy per child is impossible.
