DDSA Solutions

2226. Maximum Candies Allocated to K Children

MediumView on LeetCode
ArrayBinary Search

Problem Overview

Binary search on the answer (maximum pieces per person).

Intuition

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

Algorithm

  1. 1Binary search on value [1, max(quantity)]. Feasibility: greedily assign pieces to people sorted by quantity descending.
  2. 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
C#
// 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?

Related Problems