Minimum Number of Operations to Make Array Empty

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty/

 

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        cache = {}
        def dfs(n):
            if n < 0:
                return float("inf")
            if n in [2,3]:
                return 1
            if n in cache:
                return cache[n]

            res = min(dfs(n-2), dfs(n-3))
            cache[n] = res + 1
            return res + 1

        count = Counter(nums)
        res = 0
        for n, c in count.items():
            op = dfs(c)
            if op == float("inf"):
                return -1
            res += op
        return res

using dp and memoization.

we only focus on number of count.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        count = Counter(nums)
        res = 0

        for n , c in count.items():
            if c == 1:
                return -1
            res += math.ceil(c/3)
        return res

we can basically make any number with 2,3

for example 9 = 3 + 3 + 3  (3ops)  , 10 = (2 + 2) + 3 +3 (4ops) ,  11 = 2 + 3 + 3+ 3 (4ops)  , 12 = 3+ 3 + 3+ 3 (4ops)

100 = 3 * 33  + 1 = 3 * 32 + 2* 2  (34ops)