Sponsored
Sponsored
This approach leverages the frequency count of each number to determine the minimum number of operations needed. We will iterate over the frequency list and for each number, calculate the possible number of operations (either removing two or three elements at a time).
Time Complexity: O(n), where n is the length of the array, as we are iterating through the array and frequencies. Space Complexity: O(n) for storing the frequency count.
1#include <vector>
2#include <unordered_map>
3#include <cmath>
4
5int minOperations(std::vector<int>& nums) {
6 std::unordered_map<int, int> freq;
7 for (int num : nums) {
8 freq[num]++;
9 }
10 int operations = 0;
11 for (auto it : freq) {
12 int count = it.second;
13 if (count == 1) return -1;
14 operations += std::ceil((double)count / 3);
15 }
16 return operations;
17}We use an unordered_map to store the frequency of each element. For each element's frequency, if it is 1, we return -1 because that's insufficient for a pair or triple removal. We use ceil to find the number of times we need to perform triple operations, adding one more operation if there is a remainder. This solution is efficient as it leverages hash tables to maintain frequency counts.
This approach targets optimizing operations by prioritizing pair removals wherever possible, then triples. The main idea is to use as many pair removals as possible, and only use triples to fill gaps that pairs cannot cover fully.
Time Complexity: O(n), both for listing and iterating through frequencies. Space Complexity: O(n) for the frequency map.
1using System;
2using System.Collections.Generic;
public class Solution {
public int MinOperations(int[] nums) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (var num in nums) {
if (!freq.ContainsKey(num)) {
freq[num] = 0;
}
freq[num]++;
}
int operations = 0;
foreach (var kvp in freq) {
int count = kvp.Value;
if (count == 1) return -1;
while (count >= 2) {
if (count == 2 || count == 5) {
count -= 2;
} else {
count -= 3;
}
operations++;
}
}
return operations;
}
}Dictionary captures frequency, which is then managed within a while loop using a greedy method to minimize operations. Triples are prioritized with pairs as fallback for counts of 2 or 5, ensuring optimal operation numbers.