diff options
-rw-r--r-- | max_candies_allocated_k_children.c | 32 | ||||
-rw-r--r-- | max_candies_allocated_k_children.py | 34 |
2 files changed, 66 insertions, 0 deletions
diff --git a/max_candies_allocated_k_children.c b/max_candies_allocated_k_children.c new file mode 100644 index 0000000..45f105c --- /dev/null +++ b/max_candies_allocated_k_children.c @@ -0,0 +1,32 @@ +// 2226. Maximum Candies Allocated to K Children +#include "leetcode.h" + +/* + * 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 + */ + +int maximumCandies(int *candies, int candiesSize, long long k) { + int l = 0, r = 1e7; + while (l < r) { + long long mid = (l + r + 1) / 2, cnt = 0; + for (int i = 0; i < candiesSize && cnt < k; ++i) + cnt += candies[i] / mid; + if (cnt >= k) + l = mid; + else + r = mid - 1; + } + return l; +} + +int main() { + int c1[] = {5, 8, 6}, c2[] = {2, 5}; + printf("%d\n", maximumCandies(c1, ARRAY_SIZE(c1), 3)); // expect: 5 + printf("%d\n", maximumCandies(c2, ARRAY_SIZE(c2), 11)); // expect: 0 +} diff --git a/max_candies_allocated_k_children.py b/max_candies_allocated_k_children.py new file mode 100644 index 0000000..139ab80 --- /dev/null +++ b/max_candies_allocated_k_children.py @@ -0,0 +1,34 @@ +# 2226. Maximum Candies Allocated to K Children + +""" +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 +""" + + +class Solution(object): + def maximumCandies(self, candies, k): + """ + :type candies: List[int] + :type k: int + :rtype: int + """ + l, r = 0, sum(candies) / k + while l < r: + mid = (l + r + 1) / 2 + if k > sum(i / mid for i in candies): + r = mid - 1 + else: + l = mid + return l + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumCandies(candies=[5, 8, 6], k=3)) + print(obj.maximumCandies(candies=[2, 5], k=11)) |