LeetCode Entry

2305. Fair Distribution of Cookies

1.07.2023 medium 2023 kotlin

Min of the max distributing n cookies to k children

2305. Fair Distribution of Cookies medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/262

Problem TLDR

Min of the max distributing n cookies to k children

Intuition

Search all possible ways to give current cookie to one of the children. Backtrack sums and calculate the result.

Approach

Just DFS

Complexity

  • Time complexity: \(O(k^n)\)

  • Space complexity: \(O(2^n)\)

Code


fun distributeCookies(cookies: IntArray, k: Int): Int {
    fun dfs(pos: Int, children: IntArray): Int {
        if (pos == cookies.size) return if (children.contains(0)) -1 else children.max()!!
        var min = -1
        for (i in 0 until k) {
            children[i] += cookies[pos]
            val res = dfs(pos + 1, children)
            if (res != -1) min = if (min == -1) res else minOf(min, res)
            children[i] -= cookies[pos]
        }
        return min
    }
    return dfs(0, IntArray(k))
}