Maximum Candies Allocated to K Children

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:

• calculate the midpoint, mid
• if divideCandies returns true
  • set ans = mid
    • so we can always keep track of the values which make it possible to allocate candies to each child
  • set left = mid + 1
• if divideCandies returns false
  • set right = mid - 1

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

• Time: O(n log (m)) if n = candies.size() and m = sum(candies)/k
• Space: O(1)