Blog

Leetcode: 2305. Fair Distribution of Cookies Solution

Question Link:- https://leetcode.com/problems/fair-distribution-of-cookies/description

2305. Fair Distribution of Cookies Solution Approach

In this question, I have an array of cookies and an integer k.

I need to distribute these cookies to k children.

Such that the one which gets maximum of these is the smallest possible value.

  • 2 <= cookies.length <= 8
  • 1 <= cookies[i] <= 105
  • 2 <= k <= cookies.length

The constraints given in the question are fairly small.

Which means simple backtracking will easily pass.

Reasoning:

  1. Create a k sized array.
  2. Try to distribute the cookies in different possible ways to k children.
  3. Find max of that k sized array.
  4. And return min of these max values overall.

2305. Fair Distribution of Cookies Solution Code C++

class Solution {
public:
    int dfs(int ind, vector<int>& cookieDistributed, vector<int>& cookies, int k) {
        // if all cookies distributed
        if(ind == cookies.size()) {
            auto maxV = max_element(cookieDistributed.begin(), cookieDistributed.end());
            if(maxV!=cookieDistributed.end()) {
                int ans = *maxV;
                return ans;
            }
            return INT_MAX;
        }
        int res = INT_MAX;
        // try all ways to distribute the current cookie bag
        for(int i = 0; i < k; i++) {
            cookieDistributed[i] += cookies[ind];
            res = min(res, dfs(ind+1, cookieDistributed, cookies, k));
            cookieDistributed[i] -= cookies[ind];
        }
        return res;
    }
    int distributeCookies(vector<int>& cookies, int k) {
        // cookies Distributed
        vector<int> cookieDistributed(k, 0);
        return dfs(0, cookieDistributed, cookies, k);
    }
};

Thinking Of a More Optimized Approach

Can we do better?

This is O(k^n) Time complexity.

Maybe just more pruning. But even leetcode editorial stopped here.

I am thinking of some memoization. Why can it not be possible here?

You could conceptually do:

dp[ind][cookieDistributed] = minimum possible final maximum

But cookieDistributed is something like:

[7, 4, 9]

and later:

[4, 7, 9]

are actually equivalent states because the children are interchangeable.

So you’d need to serialize/canonicalize the vector:

sort(cookieDistributed.begin(), cookieDistributed.end());

and use that as a map key.

For example:

map<pair<int, vector<int>>, int> dp;

Then:

int dfs(int ind, vector<int>& dist, vector<int>& cookies, int k) {

    sort(dist.begin(), dist.end());

    auto key = make_pair(ind, dist);

    if (dp.count(key))
        return dp[key];

    if (ind == cookies.size())
        return dp[key] = dist.back();

    int ans = INT_MAX;

    for (int i = 0; i < k; i++) {

        dist[i] += cookies[ind];

        ans = min(ans, dfs(ind + 1, dist, cookies, k));

        dist[i] -= cookies[ind];
    }

    return dp[key] = ans;
}

But this isn’t usually what we’d call a nice DP solution. The state space can still be large.

That’s where we can use bitmask DP.

But then will greedy work??

I don’t think there’s any possibility.

So, let’s leave it here for now.

Leave a Reply