# Maximum Candies Allocated to K Children
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-candies-allocated-to-k-children)
Canonical: https://scaleengineer.com/dsa/problems/maximum-candies-allocated-to-k-children
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `candies`. Each element in the array denotes a pile of candies of size `candies[i]`. You can divide each pile into any number of **sub piles**, but you **cannot** merge two piles together.

You are also given an integer `k`. You should allocate piles of candies to `k` children such that each child gets the **same** number of candies. Each child can be allocated candies from **only one** pile of candies and some piles of candies may go unused.

Return _the **maximum number of candies** each child can get._

**Example 1:**

**Input:** candies = [5,8,6], k = 3
**Output:** 5
**Explanation:** We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

**Example 2:**

**Input:** candies = [2,5], k = 11
**Output:** 0
**Explanation:** There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

**Constraints:**

* `1 <= candies.length <= 105`
* `1 <= candies[i] <= 107`
* `1 <= k <= 1012`

# Approaches
## Brute Force (Linear Search)
This approach involves checking every possible value for the number of candies, `c`, that each child can receive. We want to find the maximum `c`, so it's logical to start checking from the highest possible value downwards. The highest possible value for `c` cannot exceed the size of the largest candy pile.
**Time:** O(N * M), where `N` is the number of piles (`candies.length`) and `M` is the maximum number of candies in a single pile. The outer loop runs up to `M` times, and the inner loop runs `N` times. This is too slow for the given constraints and will result in a Time Limit Exceeded error. · **Space:** O(1), as we only use a few variables to store the counts and loop indices.
**Pros:** The logic is straightforward and easy to implement.
**Cons:** Extremely inefficient due to the large search space for the number of candies.; Will not pass the time limits for the given constraints.
### Explanation
The algorithm iterates through all possible answers for the number of candies, `c`, starting from a maximum possible value down to 1.
The maximum possible value for `c` is the largest pile in the `candies` array, as we cannot give a child more candies than what's available in any single pile.
For each value of `c`, we check if it's possible to provide `c` candies to `k` children. This is done by calculating how many children can be satisfied from all piles combined. For a pile of size `p`, we can create `p / c` sub-piles of size `c`. We sum this value over all piles.
If the total number of children we can satisfy is greater than or equal to `k`, we have found a valid `c`. Since we are iterating downwards, the first `c` we find will be the maximum possible. We can immediately return this value.
If the loop completes without finding any valid `c` (i.e., we check all the way down to 1 and none work), it means it's impossible to give even one candy to each child. In this case, the answer is 0.
```java
class Solution {
    public int maximumCandies(int[] candies, long k) {
        int maxCandiesInPile = 0;
        for (int c : candies) {
            maxCandiesInPile = Math.max(maxCandiesInPile, c);
        }

        // Iterate from the max possible answer downwards
        for (int c = maxCandiesInPile; c >= 1; c--) {
            long childrenCanGet = 0;
            for (int pile : candies) {
                childrenCanGet += pile / c;
            }
            if (childrenCanGet >= k) {
                return c; // Found the largest possible value
            }
        }

        return 0; // Cannot even give 1 candy to each child
    }
}
```
### Algorithm
- Find the maximum value `max_val` in the `candies` array.
- Loop for `c` from `max_val` down to `1`.
- Inside the loop, initialize a counter `satisfied_children = 0`.
- Iterate through each `pile` in the `candies` array.
- Add `pile / c` to `satisfied_children`.
- After iterating through all piles, check if `satisfied_children >= k`.
- If it is, `c` is the maximum possible answer. Return `c`.
- If the loop finishes, it means no `c >= 1` is possible. Return `0`.

## Binary Search on the Answer
A more efficient approach utilizes binary search on the possible answer. The core observation is that the problem has a monotonic property: if we can give `c` candies to each of the `k` children, we can also certainly give `c-1` candies. Conversely, if we cannot give `c` candies, we also cannot give `c+1` candies. This monotonicity allows us to binary search for the maximum possible value of `c`.
**Time:** O(N * log(M)), where `N` is `candies.length` and `M` is the maximum possible value of the answer (the search space size, e.g., `10^7`). The binary search takes `log(M)` steps, and each step involves iterating through the `N` piles, taking `O(N)` time. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Very efficient and guaranteed to pass within the time limits.; It's the optimal way to solve problems with this monotonic property.
**Cons:** The concept of binary searching on the answer might be slightly less intuitive than a direct brute-force approach.
### Explanation
We define a search space for the answer `c`. The minimum possible answer is 0, and the maximum is bounded by the largest candy pile (or `10^7` from the constraints). Let's set our search range from `low = 1` to `high = 10^7`. The answer `0` can be handled as the default if no solution `c >= 1` is found.
We apply a standard binary search algorithm. In each step, we pick a `mid` value from the current range `[low, high]`.
We then have a helper function, `can_give(c)`, which checks if it's possible to give `c` candies to `k` children. This function iterates through all candy piles and sums up the number of children that can be satisfied: `total_children = sum(pile / c)`. It returns `true` if `total_children >= k`, and `false` otherwise. Note that `total_children` can be large, so it should be a `long`.
If `can_give(mid)` is `true`, it means `mid` is a possible answer. Since we want to maximize the answer, we store `mid` as a potential result and try to find an even larger value by searching in the right half of the range: `low = mid + 1`.
If `can_give(mid)` is `false`, it means `mid` is too large. We must reduce the number of candies, so we search in the left half: `high = mid - 1`.
The binary search continues until `low > high`. The last successfully recorded `mid` value will be our maximum possible answer.
```java
class Solution {
    public int maximumCandies(int[] candies, long k) {
        int low = 1;
        int high = 10_000_000; // Max value of candies[i]
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // mid can't be 0 in this loop setup, but as a safeguard
            if (mid == 0) {
                low = 1;
                continue;
            }

            if (canGive(candies, k, mid)) {
                // mid is a possible answer, try for a larger one
                ans = mid;
                low = mid + 1;
            } else {
                // mid is too large, try a smaller one
                high = mid - 1;
            }
        }
        return ans;
    }

    // Helper function to check if we can give 'c' candies to 'k' children
    private boolean canGive(int[] candies, long k, int c) {
        long childrenCount = 0;
        for (int pile : candies) {
            childrenCount += (long) pile / c;
        }
        return childrenCount >= k;
    }
}
```
### Algorithm
- Initialize `low = 1`, `high = 10^7` (a safe upper bound for the answer), and `ans = 0`.
- Start a `while` loop that continues as long as `low <= high`.
- Calculate `mid = low + (high - low) / 2`.
- Check if it's possible to give `mid` candies to `k` children:
    - Initialize `children_count = 0L`.
    - For each `pile` in `candies`, add `pile / mid` to `children_count`.
    - If `children_count >= k`, it's possible.
- If it's possible to give `mid` candies:
    - This `mid` is a potential answer. Store it: `ans = mid`.
    - Try for a larger answer: `low = mid + 1`.
- If it's not possible:
    - `mid` is too large. Try for a smaller answer: `high = mid - 1`.
- After the loop terminates, `ans` holds the maximum number of candies. Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  int maximumCandies(int[] candies, long k) {
    int left = 0, right = (int)1 e7;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      long cnt = 0;
      for (int v : candies) {
        cnt += v / mid;
      }
      if (cnt >= k) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumCandies(vector<int> &candies, long long k) {
    int left = 0, right = 1e7;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      long long cnt = 0;
      for (int &v : candies)
        cnt += v / mid;
      if (cnt >= k)
        left = mid;
      else
        right = mid - 1;
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int: left, right = 0, max(candies) while left < right: mid = (left + right + 1) >> 1 cnt = sum(v // mid for v in candies) if cnt >= k: left = mid else: right = mid - 1 return left

```