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 $\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.

Java

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 $\text{N}$ bags of cookies to distribute among $\text{K}$ children.

Time Complexity

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

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

Space Complexity

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

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