2305. Fair Distribution of Cookies LeetCode Solution
In this guide, you will get 2305. Fair Distribution of Cookies LeetCode Solution with the best time and space complexity. The solution to Fair Distribution of Cookies problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
2305. Fair Distribution of Cookies LeetCode Solution in C++
class Solution {
public:
int distributeCookies(vector<int>& cookies, int k) {
int ans = INT_MAX;
dfs(cookies, 0, k, vector<int>(k), ans);
return ans;
}
private:
void dfs(const vector<int>& cookies, int s, int k, vector<int>&& children,
int& ans) {
if (s == cookies.size()) {
ans = min(ans, ranges::max(children));
return;
}
for (int i = 0; i < k; ++i) {
children[i] += cookies[s];
dfs(cookies, s + 1, k, std::move(children), ans);
children[i] -= cookies[s];
}
}
}; /* code provided by PROGIEZ */
2305. Fair Distribution of Cookies LeetCode Solution in Java
class Solution {
public int distributeCookies(int[] cookies, int k) {
dfs(cookies, 0, k, new int[k]);
return ans;
}
private int ans = Integer.MAX_VALUE;
private void dfs(int[] cookies, int s, int k, int[] children) {
if (s == cookies.length) {
ans = Math.min(ans, Arrays.stream(children).max().getAsInt());
return;
}
for (int i = 0; i < k; ++i) {
children[i] += cookies[s];
dfs(cookies, s + 1, k, children);
children[i] -= cookies[s];
}
}
} // code provided by PROGIEZ
2305. Fair Distribution of Cookies LeetCode Solution in Python
class Solution:
def distributeCookies(self, cookies: list[int], k: int) -> int:
ans = math.inf
def dfs(s: int, children: list[int]) -> None:
nonlocal ans
if s == len(cookies):
ans = min(ans, max(children))
return
for i in range(k):
children[i] += cookies[s]
dfs(s + 1, children)
children[i] -= cookies[s]
dfs(0, [0] * k)
return ans # code by PROGIEZ
