Intuition behind Binary Search on Answers
\n\nWhen there are multiple answers that are valid but we need to find the maximum possible valid answer or minimum possible valid answer then we can use binary
<br>\n\n`When there are multiple answers that are valid but we need to find the maximum possible valid answer or minimum possible valid answer then we can use binary search on answers.`\n\n**How does it work ?**\n\nin this problem we know that minimum number of candies that we can allocate is 0 and maximum is max(candies), so in all such problems we need to find the **minimum possible answer** and **maximum possible answer** and binary search between them to find **maximum / minimum valid answer** in logarithmic time.\n\nAnd binary search on answers can be used only in those problems in which **we can validate whether the current answer in valid or not**. In this problem we can do that by checking if we can allocate x number of candies among k children by dividing some piles, so we can do binary search here.\n\n<br>\n\n```\nclass Solution {\npublic:\n    int maximumCandies(vector<int>& candies, long long k) {\n        \n        int left = 1, ans = 0;\n        int right = *max_element(candies.begin(), candies.end());\n        \n        while(left <= right) {\n            int mid = left + (right - left) / 2;\n            if(canAllocate(candies, k, mid)) {\n                left = mid + 1;\n                ans = mid;\n            }\n            else {\n                right = mid - 1;\n            }\n        }\n        \n        return ans;\n    }\n\nprivate:\n    bool canAllocate(vector<int>& candies, long long k, int candy) {\n        \n        long long total = 0;\n        \n        for(int c: candies) {\n            total += c / candy;\n            if(total >= k) return true;\n        }\n        \n        return false;\n    }\n};\n```\n<br>\n\n**Time complexity: O(n) * log(max(candies))\nSpace complexity: O(1)**\n\n<br>
['Binary Search', 'C', 'Binary Tree']