2305. Fair Distribution of Cookies Medium

1/**
2 * [2305] Fair Distribution of Cookies
3 *
4 * You are given an integer array cookies, where cookies[i] denotes the number of cookies in the i^th 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.
5 * The unfairness of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.
6 * Return the minimum unfairness of all distributions.
7 *  
8 * Example 1:
9 *
10 * Input: cookies = [8,15,10,20,8], k = 2
11 * Output: 31
12 * Explanation: One optimal distribution is [8,15,8] and [10,20]
13 * - The 1^st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
14 * - The 2^nd child receives [10,20] which has a total of 10 + 20 = 30 cookies.
15 * The unfairness of the distribution is max(31,30) = 31.
16 * It can be shown that there is no distribution with an unfairness less than 31.
17 *
18 * Example 2:
19 *
20 * Input: cookies = [6,1,3,2,2,4,1,2], k = 3
21 * Output: 7
22 * Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2]
23 * - The 1^st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
24 * - The 2^nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
25 * - The 3^rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies.
26 * The unfairness of the distribution is max(7,7,7) = 7.
27 * It can be shown that there is no distribution with an unfairness less than 7.
28 *
29 *  
30 * Constraints:
31 *
32 * 2 <= cookies.length <= 8
33 * 1 <= cookies[i] <= 10^5
34 * 2 <= k <= cookies.length
35 *
36 */
37pub struct Solution {}
38use std::cmp;
39// problem: https://leetcode.com/problems/fair-distribution-of-cookies/
40// discuss: https://leetcode.com/problems/fair-distribution-of-cookies/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn distribute_cookies(cookies: Vec<i32>, k: i32) -> i32 {
46        let mut children = vec![0; k as usize];
47        let mut result = i32::MAX;
48
49        Self::back(&cookies, k, &mut result, 0, &mut children);
50        result
51    }
52
53    fn back(cookies: &Vec<i32>, k: i32, result: &mut i32, current: usize, children: &mut Vec<i32>) {
54        if current == cookies.len() {
55            let mut min = 0;
56            for c in children.iter() {
57                min = cmp::max(min, *c);
58            }
59
60            *result = cmp::min(*result, min);
61
62            return;
63        }
64
65        for i in 0..k {
66            children[i as usize] += cookies[current];
67            Self::back(cookies, k, result, current + 1, children);
68            children[i as usize] -= cookies[current];
69        }
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_2305() {
81        assert_eq!(Solution::distribute_cookies(vec![8, 15, 10, 20, 8], 2), 31);
82        assert_eq!(
83            Solution::distribute_cookies(vec![6, 1, 3, 2, 2, 4, 1, 2], 3),
84            7
85        );
86    }
87}
88