LeetCode Entry

2226. Maximum Candies Allocated to K Children

14.03.2025 medium 2025 kotlin rust

Distribute candies to k equal buckets search

2226. Maximum Candies Allocated to K Children medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/927

Problem TLDR

Distribute candies to k equal buckets #medium #binary_search

Intuition

Binary search in a space of k: check range 1..max(candies), try to take candies to the sum. If it possible, try a bigger pile.

Follow up: what if candies is already sorted? Is there O(n) algorithm? (I can’t find it)

Approach

• calculate result in a separate variable res = max(res, m) to be safe, but you can golf and just use the hi variable as answer

Complexity

• Time complexity: \(O(nlog(max))\)

• Space complexity: \(O(1)\)

Code

    fun maximumCandies(candies: IntArray, k: Long): Int {
        var lo = 1; var hi = candies.max()
        while (lo <= hi) {
            val m = lo + (hi - lo) / 2
            if (k <= candies.sumOf { 1L * it / m })
            lo = m + 1 else hi = m - 1
        }
        return hi
    }

    pub fn maximum_candies(candies: Vec<i32>, k: i64) -> i32 {
        let (mut lo, mut hi) = (1, 10_000_000);
        while lo <= hi {
            let m = lo + (hi - lo) / 2;
            if k <= candies.iter().map(|&x| x as i64 / m).sum()
            { lo = m + 1 } else { hi = m - 1 }
        } hi as _
    }

    int maximumCandies(vector<int>& candies, long long k) {
        int lo = 1, hi = 10000000;
        while (lo <= hi) {
            int m = lo + (hi - lo) / 2; long s = 0;
            for (int c: candies) s += 1L * c / m;
            k > s ? hi = m - 1 : lo = m + 1;
        } return hi;
    }