Skip to main content

2305. Fair Distribution of Cookies

This page provides solutions for the leetcode problem 2305. Fair Distribution of Cookies.

Problem Explanation​

The problem is asking us to divide the cookies among K\text{K} children in such a way that the maximum number of cookies a single child gets is minimized.

Solution​

For this problem, we need to consider all possible distribution possibilities. Therefore, we use the backtracking technique. More such problem can be found here.

class Solution {
  private int min = Integer.MAX_VALUE;

  public int distributeCookies(int[] cookies, int k) {
    backtrack(cookies, 0, new int[k]);
    return min;
  }

  private void backtrack(int[] cookies, int index, int[] dist) {
    if(index == cookies.length) min = Math.min(min, max(dist));
    else {
      for(int i = 0; i < dist.length; i++) {
        if(dist[i] + cookies[index] >= min) continue;
        dist[i] += cookies[index]; 
        backtrack(cookies, index + 1, dist);
        dist[i] -= cookies[index];
      }
    }
  }

  private int max(int[] dist) {
    int maxValue = Integer.MIN_VALUE;
    for(int i = 0; i < dist.length; i++) maxValue = Math.max(maxValue, dist[i]);
    return maxValue;
  }
}

Complexity​

Let's say there are N\text{N} bags of cookies to distribute among K\text{K} children.

Time Complexity​

Each of the N\text{N} bag has K\text{K} options to choose from.

O(KN)\text{O}(\text{K} ^ \text{N})

Space Complexity​

Since there are N\text{N} bags to assign to each child, the stack size for the backtracking will go upto N\text{N}. Additionally, an array of size K\text{K} is needed to hold the distribution of bags among the K\text{K} children.

O(N+K)O(\text{N} + \text{K})