{"id":9623,"date":"2022-04-02T23:08:13","date_gmt":"2022-04-03T06:08:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9623"},"modified":"2022-04-02T23:08:59","modified_gmt":"2022-04-03T06:08:59","slug":"leetcode-2226-maximum-candies-allocated-to-k-children","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-2226-maximum-candies-allocated-to-k-children\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2226. Maximum Candies Allocated to K Children"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> integer array candies<\/code>. Each element in the array denotes a pile of candies of size candies[i]<\/code>. You can divide each pile into any number of sub piles<\/strong>, but you cannot<\/strong> merge two piles together.<\/p>\n\n\n\n

You are also given an integer k<\/code>. You should allocate piles of candies to k<\/code> children such that each child gets the same<\/strong> number of candies. Each child can take at most one<\/strong> pile of candies and some piles of candies may go unused.<\/p>\n\n\n\n

Return the maximum number of candies<\/strong> each child can get.<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> candies = [5,8,6], k = 3\nOutput:<\/strong> 5\nExplanation:<\/strong> 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.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> candies = [2,5], k = 11\nOutput:<\/strong> 0\nExplanation:<\/strong> 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.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= candies.length <= 105<\/sup><\/code><\/li>
  • 1 <= candies[i] <= 107<\/sup><\/code><\/li>
  • 1 <= k <= 1012<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Binary Search<\/strong><\/h2>\n\n\n\n
    Find the smallest L s.t. we can allocate candies to less than k children.<\/p>\n\n\n\n
    ans = L – 1.<\/p>\n\n\n\n
    Time complexity: O(nlogm) where n is number of piles, m is sum(candies) \/ k.
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximumCandies(vector& candies, long long k) {\n    long long total = accumulate(begin(candies), end(candies), 0LL);\n    long long l = 1;\n    long long r = total \/ k + 1;\n    while (l < r) {\n      long long m = l + (r - l) \/ 2;\n      long long c = 0;\n      for (int pile : candies)\n        c += pile \/ m;\n      if (c < k)\n        r = m;\n      else\n        l = m + 1;\n    }\n    return l - 1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,177],"class_list":["post-9623","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9623","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9623"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9623\/revisions"}],"predecessor-version":[{"id":9625,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9623\/revisions\/9625"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9623"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9623"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9623"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}