2226: Maximum-Candies-Allocated-to-K-Children
Medium

table of contents

Binary Search is the name of the game.

We just binary search for the maximum number of candies each child can get. We first initialize left and right to be the smallest and largest possible candy count to be allocated.

Then, we can just run a normal binary search with our helper function divideCandies, that aims to check whether dividing by target candies is feasible or not. Now, while left <= right:

Finally, we can just return ans.

code

// this helper function checks whether dividing by `target` candies is feasible or not
class Solution {
public:
    bool divideCandies(vector<int>& candies, int target, int long long k) {
        long long counter = 0;
        for (int &candy : candies) {
            counter += candy/target;
            if (counter >= k) {
                return true;
            }
        }
        return false;
    }
    int maximumCandies(vector<int>& candies, long long k) {
        int left = 1;
        long long sum = 0;
        for (int& candy : candies) {
            sum += candy;
        }
        int right = sum/k;

        int mid;
        int ans = 0;

        while (left <= right) {
            mid = left - (left - right)/2;
            if (divideCandies(candies, mid, k)) {
                ans = mid;
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return ans;        
    }
};

complexity