[Solved] Fair Distribution of Cookies LeetCode Contest Problem

Fair Distribution of Cookies: You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith bag. You are also given an integer k that denotes the number of children to distribute all the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.

The unfairness of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.

Return the minimum unfairness of all distributions.

Example 1:

Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Explanation: One optimal distribution is [8,15,8] and [10,20]
- The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies.
The unfairness of the distribution is max(31,30) = 31.
It can be shown that there is no distribution with an unfairness less than 31.

Example 2:

Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies.
The unfairness of the distribution is max(7,7,7) = 7.
It can be shown that there is no distribution with an unfairness less than 7.

Constraints:

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

Solution:

Time Complexity: O(k^n)

class Solution {
  public:

    int distributeCookies(vector < int > & a, int k) {
      int ans = 1000000000;
      vector < vector < int >> bucket;
        
      //create K empty buckets
      for (int i = 0; i < k; i++) {
        bucket.push_back({});
      }
      back(a, a.size(), k, 0, bucket, ans);
      return ans;
    }

  void back(vector < int > a, int n, int k, int i, vector < vector < int >> bucket, int & ans) {
    if (i == n) {
      if (k == 0) {
        int maxi = -1;
        for (auto array: bucket) 
        {
          int sum = 0;
            
          for (auto val: array)
            sum += val;

          maxi = max(maxi, sum);
        }

        ans = min(ans, maxi); // here we are calculating final ans
      }
      return;
    }
    for (int j = 0; j < bucket.size(); j++) {
      if (bucket[j].size() == 0)
      {
        bucket[j].push_back(a[i]);
        back(a, n, k - 1, i + 1, bucket, ans);
        bucket[j].pop_back();
		break;
      } 
       else
      {
        bucket[j].push_back(a[i]);
        back(a, n, k, i + 1, bucket, ans);
        bucket[j].pop_back();
      }
    }
  }
};

Intuition: Simply generate all possible cases using backtracking, and maintain the total cookies for every child.

Steps:

1. use an array children to store the total cookies for each child
2. for each cookie, try to distribute it to any child
3. if all the cookies are distributed (current index == cookies.length), find the maximum cookie among children and update the result

Complexity:

Time: O(k^n) where n = cookies.length
Space: O(k+n) k is the children array, n is the number of call stacks

int res = Integer.MAX_VALUE;
public int distributeCookies(int[] cookies, int k) {
    dfs(cookies, 0, k, new int[k]);
    return res;
}

void dfs(int[] cookies, int cur, int k, int[] children) {
    if (cur == cookies.length) {
        int max = 0;
        for (int c : children) max = Math.max(max, c);
        res = Math.min(res, max);
        return;
    }
    for (int i = 0; i < k; i++) {
        children[i] += cookies[cur];
        dfs(cookies, cur + 1, k, children);
        children[i] -= cookies[cur];
    }
}

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        ans = float('inf')
        fair = [0]*k
        def rec(i):
            nonlocal ans,fair
            if i == len(cookies):
                ans = min(ans,max(fair))
                return
            if ans <= max(fair):
                return
            for j in range(k):
                fair[j] += cookies[i]
                rec(i+1)
                fair[j] -= cookies[i]
        rec(0)
        return ans

Happy Learning – If you require any further information, feel free to contact me.