Binary Search | C++ Easy | O(N log K) | Detailed Explanation of each step
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve this problem, you can use binary search to efficiently find the maximum number
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve this problem, you can use binary search to efficiently find the maximum number of candies that can be allocated to each child. The key observation is that if it\'s possible to allocate mid candies to each child, then it\'s also possible to allocate any number less than mid. Conversely, if it\'s not possible to allocate mid candies to each child, then it\'s also not possible to allocate any number greater than mid. This binary search approach helps narrow down the search space quickly.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Calculate the sum of all candies in the candies array, denoted by sum.\n2. Set the initial search space boundaries: s = 1 (minimum candies per child) and e = sum (maximum candies per child).\n3. Perform a binary search on the search space (s to e).\n4. In each iteration of the binary search, calculate the mid-point (mid) and check if it\'s possible to allocate mid candies to each child using the isPossible function.\n5. If it\'s possible, update the answer (ans) to mid and adjust the search space to the right (s = mid + 1).\n6. If it\'s not possible, adjust the search space to the left (e = mid - 1).\n7. Continue the binary search until the search space is exhausted (s > e).\n8. Return the maximum number of candies (ans) found during the search.\n\nThe isPossible() function checks if it\'s possible to allocate a certain number of candies (mid) to each child by iterating through the piles and counting how many candies each child would get. If the total count is greater than or equal to k, it\'s possible.\n\nThis approach efficiently finds the maximum number of candies that can be allocated to each child while adhering to the given constraints. The use of binary search ensures a logarithmic time complexity.\n\n\n# Complexity\n- Time complexity: O(N log K), where N is the number of elements in the candies array, and K is the sum of all candies in the array.\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    bool isPossible(vector<int>& candies, long long mid, long long k){\n        long long count=0;\n        for(int i=0; i<candies.size(); i++){\n            int x=candies[i];\n            count+=(x/mid);\n        }\n        if(count>=k){\n            return true;\n        }\n        else{ \n            return false;\n        }\n    }\n    int maximumCandies(vector<int>& candies, long long k) {\n        int s=1;\n        long long e, sum=0;\n        long long ans=0;\n\n        for(int i=0; i<candies.size();i++){\n            sum+=candies[i];\n        }\n        e=sum;\n        if(sum==k){\n            return 1;\n        }\n        else if(sum<k){\n            return 0;\n        }\n        else{\n        long long mid=s+(e-s)/2;\n\n        while(s<=e){\n            if(isPossible(candies,mid,k)){\n                ans = max(ans,mid);\n                s=mid+1;\n            }\n            else{\n                e=mid-1;\n            }\n            mid=s+(e-s)/2;\n        }\n        return ans;\n        }\n    }\n};\n```\n
['Binary Search', 'C++']