medium Fair Distribution of Cookies

Problem Statement

You are given an array of integers cookies, where cookies[i] represents the count of cookies in the i^th bag, and integer k that represents the number of children. You must divide these bags among k children such that every bag goes entirely to one child, with no splitting of the contents.

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

Return the minimum unfairness of all distributions.

Examples

1. Example 1:

   • Input: cookies = [5,6,7,3,4], k = 2
   • Expected Output: 13
   • Justification: The most balanced way to distribute the cookies is to give bags [5,7] to one child and [6,3,4] to the other, resulting in one child getting 13 cookies and the other getting 12. The maximum number of cookies received by a child is 13, which is the minimal unfairness possible here.

2. Example 2:

   • Input: cookies = [1,2,3,4,5,6,7,8], k = 3
   • Expected Output: 12
   • Justification: An optimal distribution would give bags [4, 8], [5, 7], and [1, 2, 3, 6] to the three children. This way, the maximum cookies any child gets is 12, which is the best minimal unfairness achievable with this setup.

3. Example 3:

   • Input: cookies = [10,10,10,10], k = 4
   • Expected Output: 10
   • Justification: Since there are equal numbers of cookies in each bag and the same number of children as there are bags, the fairest distribution is straightforward: each child gets one bag. The maximum cookies received by any child is 10, which is the lowest possible unfairness.

Solution

To solve this problem, we approach it with a backtracking algorithm that systematically explores all possible distributions of cookies to the children. The algorithm aims to minimize the maximum number of cookies received by any child. By considering each bag of cookies one at a time and deciding which child to give it to, we can explore the entire space of distributions.

The reason this approach is effective is that it allows us to exhaust all possibilities and choose the one with the least unfairness. It's akin to searching through a tree where each node represents a decision (which child gets the next bag of cookies), and we are trying to find the leaf node with the minimum value of the maximum cookies received by any child. The backtracking aspect is crucial because it enables us to undo decisions and explore different paths in the search tree, ensuring we find the optimal solution.

Step-by-Step Algorithm

1. Initialize Variables and Start the Process:

   • Initializes the process by calling the backtrack method with the initial state: the cookies array, index 0 (starting point), an array to keep track of the total cookies each child has received (initialized with zeros and of length k), and Integer.MAX_VALUE (or an equivalent large value) to represent the initial minimal unfairness.

2. Base Case Check:

   • Inside the backtracking function, check if the current index matches the length of the cookies array. If it does, calculate the current distribution's unfairness by finding the maximum value in the children array (the most cookies any child has received). Compare this with the current minimal unfairness and update the minimal unfairness to be the smaller of the two. Return this updated minimal unfairness value.

3. Recursive Exploration:

   • If the base case condition is not met, iterate over each child, attempting to distribute the current cookie to each child one by one. For each child:
     • Add the number of cookies in the current bag (indicated by the current index) to the total cookies of the child being considered.
     • Recursively call the backtrack function with the next index (current index + 1) to consider the next bag of cookies, and pass the updated minimal unfairness value. This recursive call will return an updated minimal unfairness, which considers the addition of the current cookie to the current child.
     • Subtract the number of cookies in the current bag from the total cookies of the child being considered to undo the current distribution step (backtrack), enabling the exploration of other distribution possibilities.

4. Return the Result:

   • The backtrack function returns the minimal unfairness value after exploring all possible distributions. This value is then returned by the distributeCookies method as the final result, representing the minimal unfairness achievable for the given set of cookies and number of children.

Algorithm Walkthrough

Let's consider the Input: cookies = [5,7,6,3,4], k = 2

1. Initial Call:
   • The distributeCookies method is called with cookies = [5,7,6,3,4] and k = 2.
   • This method initializes a children array with 2 elements (for 2 children), both set to 0, indicating that initially, no child has been given any cookies.
   • It then calls the backtrack method with the initial index of 0 and an initial minimal unfairness value set to Integer.MAX_VALUE.

2. Start Recursive Exploration with the First Cookie:

• Index 0, Cookies[0] = 5:
  • First child (children[0]): Attempt to give them the first cookie bag (5 cookies).
    • Update children to [5, 0].
    • Call backtrack with next index (1).

3. Continue to Second Cookie:

• Index 1, Cookies[1] = 7:
  • First child: Attempt to give them the second cookie bag (6 cookies).
    • Update children to [12, 0].
    • Call backtrack with next index (2).

4. Continue to Third Cookie:

• Index 2, Cookies[2] = 6:
  • First child: Attempt to give them the third cookie bag (7 cookies).
    • Update children to [18, 0].
    • Call backtrack with next index (3).

5. Continue to Fourth Cookie:

• Index 3, Cookies[3] = 3:
  • First child: Attempt to give them the fourth cookie bag (3 cookies).
    • Update children to [21, 0].
    • Call backtrack with next index (4).

6. Continue to Fifth Cookie:

• Index 4, Cookies[4] = 4:
  • First child: Attempt to give them the fifth cookie bag (4 cookies).
    • Update children to [25, 0]. This is the maximum unfairness when all cookies are given to the first child.
    • No more cookies left. Compute unfairness (25) and backtrack. Now, minUnfairness = 25. 7. Backtrack to index 3:
• Remove the fifth cookie bag from the first child, backtrack to fourth cookie.
• Now, attempt to give the fifth cookie bag (4 cookies) to the second child.
• Update children to [21, 4].
• Now, index = 5. So, Update minUnfairness. Now, minUnfairness = 21.

7. Backtrack to index 2:

• Remove the fourth cookie bag from the first child, backtrack to third cookie.
• Now, attempt to give the fourth cookie bag (3 cookies) to the second child.
• Update children to [18, 7] when we reach to index 5.
• Update minUnfairness when we reach to index 5. Now, minUnfairness = 18.

7. Backtrack to index 2:

• Remove the third cookie bag from the first child, backtrack to second cookie.
• Now, attempt to give the third cookie bag (6 cookies) to the second child.
• Update children to [12, 12] when we reach to index 5.
• Update minUnfairness when we reach to the index 5. Now, minUnfairness = 12.

8. Systematically Explore All Combinations:

• Continue the systematic exploration by shifting the distribution of cookies among the children at every level of recursion, ensuring every possible combination of distributions is considered. For each configuration, update the children array, compute unfairness, and compare it to the current minimum unfairness to potentially update it.

9. Return the Result:

• The distributeCookies function ultimately returns the minimal unfairness value, which is 12.

Code

import java.util.Arrays;

public class Solution {

  // Method to start the distribution process
  public int distributeCookies(int[] cookies, int k) {
    return backtrack(cookies, 0, new int[k], Integer.MAX_VALUE);
  }

  // Backtracking function to explore all possible distributions
  private int backtrack(
    int[] cookies,
    int index,
    int[] children,
    int minimalUnfairness
  ) {
    if (index == cookies.length) { // All cookies have been considered
      int maxCookie = Arrays.stream(children).max().getAsInt();
      return Math.min(minimalUnfairness, maxCookie); // Update minimalUnfairness if current distribution is better
    }

    int minUnfairness = minimalUnfairness;
    for (int i = 0; i < children.length; i++) { // Try giving current cookie to each child
      children[i] += cookies[index]; // Assign cookie to child i
      minUnfairness = backtrack(cookies, index + 1, children, minUnfairness); // Recurse for next cookie
      children[i] -= cookies[index]; // Backtrack to try another distribution
    }
    return minUnfairness;
  }

  // Main method to test the algorithm with given examples
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    System.out.println(
      solution.distributeCookies(new int[] { 5, 6, 7, 3, 4 }, 2)
    ); // Expected: 13

    // Example 2
    System.out.println(
      solution.distributeCookies(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 }, 3)
    ); // Expected: 12

    // Example 3
    System.out.println(
      solution.distributeCookies(new int[] { 10, 10, 10, 10 }, 4)
    ); // Expected: 10
  }
}

Complexity Analysis

Time Complexity

• Time Complexity: , where n is the number of cookies (or bags) and k is the number of children. This is because, for each cookie, we have k choices (which child to give the cookie to), leading to possible distributions to explore through backtracking.

Space Complexity

• Space Complexity: , where n is the depth of the recursion tree (or the number of cookies). This space is used to store the recursion call stack. The auxiliary space used to store the children's cookies count is , but since k ≤ n (in most practical scenarios, you wouldn't have more children than cookies), the dominating factor is .