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 take **at most 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 = 3Output:5Explanation: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 = 11Output:0Explanation: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 <= 10`

^{5}`1 <= candies[i] <= 10`

^{7}`1 <= k <= 10`

^{12}

**Solution: Binary Search**

Find the smallest L s.t. we can allocate candies to less than k children.

ans = L – 1.

Time complexity: O(nlogm) where n is number of piles, m is sum(candies) / k.

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int maximumCandies(vector<int>& candies, long long k) { long long total = accumulate(begin(candies), end(candies), 0LL); long long l = 1; long long r = total / k + 1; while (l < r) { long long m = l + (r - l) / 2; long long c = 0; for (int pile : candies) c += pile / m; if (c < k) r = m; else l = m + 1; } return l - 1; } }; |