< Back





2226. Maximum Candies Allocated to K Children

Another search space question. We're given piles of candies, candies[i], and k children. We asked to
find the maximum amount of candy we can give to each child from the piles. Piles can't be mixed,
however, they can be split.

Our search space will be 1, the smallest candy pile we can create, and sum(candies) // k, the largest
pile of candy we can give to a single child. We'll use binary search to find the maximum amount of
candy we can give to each child. The key for search is sum(c // m for c in candies) < k - if we can't
create enough candy piles we decrease our search space by decreasing the size of the piles, setting
r = m. Otherwise, if our candy piles are small enough to give to each child, we need to increase the
size of our piles, setting l = m + 1.

The solution is as follows:


  class Solution:
      def maximumCandies(self, candies: List[int], k: int) -> int:
          l, r = 1, sum(candies) // k

          while l <= r:
              m = (r + l) // 2

              if sum(c // m for c in candies) < k:
                  r = m - 1
              else:
                  l = m + 1

          return r


_ Time Complexity:

  O(c log(n)) - Where c is the number of candy piles and n is the maximum number of candies we can
  give to a child.

_ Space Complexity:

  O(1) - We use a constant amount of space.