Practice/Meta/Leetcode 2226. Maximum Candies Allocated to K Children

Leetcode 2226. Maximum Candies Allocated to K Children

CodingOptional

Problem

You are distributing candy to children from several bags. You have an array candies where candies[i] represents the number of candies in the i-th bag. You need to distribute candies to exactly k children.

You can split any bag into smaller portions, but you cannot combine candies from different bags. Each child must receive exactly the same number of candies. Your goal is to maximize the number of candies each child receives.

Find the maximum number of candies each child can get, or return 0 if it's impossible to distribute candies equally to all k children.

Requirements

1. Each of the k children must receive exactly the same number of candies
2. You may split bags into smaller portions of any size
3. You cannot merge or combine candies from different bags
4. Not all candies need to be distributed (leftover candies are allowed)
5. Return the maximum possible candies per child, or 0 if distribution is impossible

Constraints

• 1 ≤ candies.length ≤ 105
• 1 ≤ candies[i] ≤ 109
• 1 ≤ k ≤ 1012
• Time complexity target: O(n log m) where n is the number of bags and m is the maximum candies in a bag
• Space complexity target: O(1)

Examples

Example 1:

` Input: candies = [5, 8, 6], k = 3 Output: 5 Explanation: We can distribute 5 candies to each of 3 children:

• From bag with 5 candies: give 5 to child 1 (0 left)
• From bag with 8 candies: give 5 to child 2 (3 left)
• From bag with 6 candies: give 5 to child 3 (1 left) `

Example 2:

Input: candies = [2, 5], k = 11 Output: 0 Explanation: Total candies = 7, but we need to serve 11 children. Even giving 0 candies won't work, so we return 0.

Example 3:

` Input: candies = [4, 7, 5], k = 4 Output: 3 Explanation: We can give 3 candies to each of 4 children:

• From bag with 4: one pile of 3 (1 left)
• From bag with 7: two piles of 3 (1 left)
• From bag with 5: one pile of 3 (2 left) Total: 4 piles of 3 candies each `