Binary Search Solution with Explanation | Java | O(n log(max(candies)))
Simple Binary Search Solution | Java | O(n log(max(candies)))\n\nIdea:\nBrute force :Start with 1 candy and see if we can allocate. If yes, then check for 2 can
Simple Binary Search Solution | Java | O(n log(max(candies)))\n\n**Idea**:\nBrute force :Start with 1 candy and see if we can allocate. If yes, then check for 2 candy. \nOptimization: Instead of checking every candy at a time, why can\'t we directly check for a number to see if we can allocate that many candy. This way we reduce our search space. Best way to do it is binary search.\n\n**Approach**:\nFirst go through each pile and store the maximum of candy of that pile.\nNow your seach space will be `[0 - max]`. Now, we will pick `mid` from that and check if we can allocate that many candies to k children. If yes, update `lo`, if not update `hi`.\n0 is trickey number because you can always allocate that many candies. So, at the end I do a check one more time on lo to see if I can allocate that candies. otherwise return lo-1.\n\n**TimeComplexity**:\n`O(n)` to check if you can allocate x candies to k people\ncalling above function `log(max(candies))`.\nSo, overall time complexity `O(n log(max(candies)))`\n\n**Upvote if it helps. Thanks :)**\n\n```\nclass Solution {\n    public int maximumCandies(int[] candies, long k) {\n        \n        int max = 0;\n        for(int candy : candies)\n            max = Math.max(max, candy);\n        int lo = 0, hi = max;\n        \n        while(lo < hi) {            \n            int mid = lo + (hi-lo)/2;\n            if(canAllocate(candies, k, mid)) {\n                lo = mid+1;\n            } else {\n                hi = mid ;\n            }\n        }  \n        return canAllocate(candies, k, lo) ? lo : lo-1;\n    }\n    \n    public boolean canAllocate(int[] candies, long k, int allow) {\n        if(allow == 0)\n            return true;\n        long total = 0;\n        for(int candy : candies) {\n            total += candy / allow;\n            if(total >= k)\n                return true;\n        }\n        return false;\n    }\n}\n```
['Binary Tree', 'Java']