C++ Binary Search
\nSee my latest update in repo LeetCode\n\n## Solution 1. Binary Answer\n\nBinary search in range L = 1, R = max(A).\n\nFor a given M = (L + R) / 2, we test if 
\nSee my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Binary Answer\n\nBinary search in range `L = 1, R = max(A)`.\n\nFor a given `M = (L + R) / 2`, we test if we can give `M` candies to each child, which can be done by traversing the array once, taking `O(N)` time. \n\nIf possible/valid, we make `L = M + 1`; otherwise, we make `R = M - 1`.\n\nIn the end, since we are looking for the greatest valid number, we return `R`.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-287/problems/maximum-candies-allocated-to-k-children/\n// Author: github.com/lzl124631x\n// Time: O(Nlog(sum(A)))\n// Space: O(1)\nclass Solution {\npublic:\n    int maximumCandies(vector<int>& A, long long k) {\n        long L = 1, R = *max_element(begin(A), end(A)), N = A.size();\n        auto valid = [&](long m) {\n            long cnt = 0;\n            for (int n : A) {\n                cnt += n / m;\n                if (cnt >= k) return true;\n            }\n            return false;\n        };\n        while (L <= R) {\n            long M = L + (R - L) / 2;\n            if (valid(M)) L = M + 1;\n            else R = M - 1;\n        }\n        return R;\n    }\n};\n```
[]