⭐Python Solution with Binary Search Explained
\nclass Solution:\n    def maximumCandies(self, candies: List[int], k: int) -> int:\n        # The lower bound is 1 and higher bound is maximum value from candi
```\nclass Solution:\n    def maximumCandies(self, candies: List[int], k: int) -> int:\n        # The lower bound is 1 and higher bound is maximum value from candies. \n        lo, hi = 1, max(candies)\n        # This higher bound is not generally possible except for cases like candies = [5,5,5,5] & k = 4\n        res = 0 # Current maximum result\n        if sum(candies) < k: # If true then we cannot give even 1 candy to each child thus return 0\n            return 0\n        \n        def cal_num_of_piles(pile_size): # Criterion function\n            count = 0\n            for c in candies:\n                count += c // pile_size\n            return count >= k\n        \n        while lo <= hi: # Binary Search Algorithm \n            mid = (lo + hi + 1) // 2 # Expected answer\n            if cal_num_of_piles(mid): # Check if mid is a possible answer.\n                res = mid # Update the current maximum answer\n                lo = mid + 1 # Check ahead of mid\n            else:\n                hi = mid - 1 # Check below mid\n        return res\n```\n\n**Concept of Binary Search on Answer:**\nThe best way to explain Binary Search the Answer is that we use binary search to guess the answer to the problem. By guessing we mean that we will get several \u201CYES\u201D or \u201CNO\u201D feedback or maybe \u201Ctoo high\u201D, \u201Ctoo low\u201D, or \u201Cexactly\u201D responses. Since we need the maximum answer Binary Search tries to converge on the largest possible answer till the possibility exists.\n\n**Binary Search on Answer has 3 basic requirements:**\n1. The problem must have multiple possible answers. **[Range of possible solutions]**\n2. The problem must be an optimization problem. **[Minimizing/Maximizing the result]**\n3. We must develope a function/criterion to determine when to update left and right pointers. **[Criterion to update pointers]**\n\n**Observations:**\n`For candies = [5,8,6] & k = 3` we have many possible answers: 1, 2, 3, 4, 5 all seem to work fine but we return 5 as it is the largest.\n1. Thus we have a range of solutions and we are asked to maximize the final result. **Requirement 1 and 2 are fulfilled**.\n2. One might feel that the possible answers must be smaller than the smallest value of an array. Eg: `for candies = [5,6,8] & k = 3` then the answer is 5. For say `candies = [7,9,13] & k = 4` the possible answers are 6, 5...2, 1. However this is not always correct. For Eg: `candies = [1,2,3,4,10] & k = 5` the possible answers are 1, 2, 3. Here we can neglect the 0th and 1st piles to get a better answer. This is because we are told that we may let some piles of candies go unused.\n3. **Developing the criterion:** Since we only need to check if a given value can be possibly divided k times with the given candies array. Hence we get an easy update function. \n\t```\n\tdef cal_num_of_piles(pile_size):\n\t\tcount = 0 # Number of divisions with current pile_size\n\t\tfor c in candies:\n\t\t\tcount += c // pile_size # Add how many piles can be generated with ith candies with given pile_size\n\t\treturn count >= k\n\t```\n***So all three requirements are now fulfilled.***\n
['Binary Tree', 'Python', 'Python3']