2226. Maximum Candies Allocated to K Children

MediumView on LeetCode

Array Binary Search

Intuition

Binary search on the answer (maximum pieces per person). Check if distributable with given max.

Algorithm

1Binary search on value [1, max(quantity)]. Feasibility: greedily assign pieces to people sorted by quantity descending.
2Sort quantities descending. For each person: assign floor(total_pieces / needed). Reduce total_pieces.

Common Pitfalls

•Sort quantities descending for greedy to work. Binary search on total pieces per person.

2226.cs

// Approach: Binary search on candy allocation; validate by summing floor(pile/mid) >= k.
// Time: O(n log(sum/k)) Space: O(1)

public class Solution
{
    public int MaximumCandies(int[] candies, long k)
    {
        long l = 1;
        long sum = 0;
        foreach (int val in candies)
            sum += val;
        long r = sum / k;

        while (l < r)
        {
            long m = (l + r) / 2;
            if (NumChildren(candies, m) < k)
                r = m;
            else
                l = m + 1;
        }

        return NumChildren(candies, l) >= k ? (int)l : (int)l - 1;
    }

    private long NumChildren(int[] candies, long m)
    {
        long sum = 0;
        foreach (int c in candies)
            sum = sum + (c / m);
        return sum;
    }
}

Was this solution helpful?