Leetcode # 2870. Minimum Number of Operations to Make Array Empty

Problem

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

Testcases

Solution

Time Complexity: O(n)
Space Complexity: O(len(set(nums)))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minOperations(self, nums: List[int]) -> int:
    counter = Counter(nums)
    result = 0
    
    @lru_cache
    def op_times(number):
      if number == 2 or number == 3:
        return 1
      result = 0
      if number % 2 == 1:
        number -= 3
        result += 1
      multiples_of_6 = number // 6
      number, result = number - 6 * multiples_of_6, result + multiples_of_6 * 2
      return result + number // 2
    
    for num in counter:
      if counter[num] == 1:
        return -1
      result += op_times(counter[num])
    return result

Last Updated on 2023/10/01 by A1go