Leetcode 2870 - Minimum Number of Operations to Make Array Empty

Link to problem

Description

You are given a 0-indexed array nums consisting of positive integers. There are two types of operations that you can apply on the array any number of times:

• Choose two elements with equal values and delete them from the array.
• Choose three elements with equal values and delete them from the array.

Return the minimum number of operations required to make the array empty, or -1 if it is not possible.

Solution

First off, since only equal values can be deleted, the position of the values in the array does not matter. So we could use a hash map to store the values in the array and its frequency.

After that, the min operations could be done by observing how number works :)

• If frequency = 1, cannot be eliminated.
• If frequency = $3n, n\in\mathbb{R}$. Operations required = $n$.
• If frequency = $3n+1 = 3(n-1) + 2\times 2$. Operations required = $(n-1)+2 = n+1$.
• If frequency = $3n+2 = 3n + 2\times 1$. Operations required = $n+1$.

Implementation

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ops = 0;
        unordered_map<int, int> hashMap;
        for (auto i: nums) {
            hashMap[i]++;
        }

        for (auto [_, count]: hashMap) {
            if (count == 1) return -1;
            ops += (count / 3) + ((count % 3 == 0)? 0: 1);
        }

        return ops;
    }
};

Or, ops += (count/3) + ((count % 3 == 0)? 0: 1) could be ops += (count + 2) / 3, as:

• $\lfloor 3n+2\rfloor/3=n$
• $\lfloor (3n+1)+2\rfloor/3=n+1$
• $\lfloor (3n+2)+2\rfloor/3=n+1$, which is exactly what we wanted.