Given an array arr[] of length N, the task is to find the minimum number of operations to change the array such that each arr[i] occurs arr[i] times where in each operation either one element can be deleted from the array or one element can be inserted in the array.
Examples:
Input: N = 4, arr[ ] = {1, 1, 3, 3}
Output: 2
Explanation: Delete one occurrence of 1 from the array in one operation.
In another operation, insert element 3 in the array.
The final array will be [ 1, 3, 3, 3 ] where 1 occurs 1 time and 3 occurs 3 times.
Minimum 2 operations are needed. It cannot be reconstructed in less than 2 moves.Input: N = 6, arr[ ] = {3, 3, 5,, 3, 2, 4}
Output: 3
Approach: The solution to the problem is based on the following idea:
For each array element (arr[i]), there are two choices: either delete all the occurrences of arr[i] or insert arr[i] such that number of occurrences is not same as its value.
Choose the minimum among the required number of deletions and insertions to minimize the total number of operations.
Follow the steps mentioned below to implement the idea:
- Store the frequency of all the elements
- Check if the frequency of the element is higher or greater than its value:
- If the frequency is higher than the best choice is to remove the element until the frequency becomes same as the current element.
- Else there are two choices:
- Delete all the occurrences of the element.
- Insert the element such that the frequency is same as its value.
- Add the minimum of these two in the final count of operations.
- Return the final count as the answer.
Below is the implementation for the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find out minimum// number of operationint minOperations(int N, vector<int>& a){ // Map for storing frequency // of the array elements unordered_map<int, int> mp; for (auto x : a) { mp[x]++; } // Variable to store the answer int operations = 0; for (auto x : mp) { int occurrences = x.second; // If the occurrence is greater // than number then the greedy // move is to remove extra occurrences if (occurrences > x.first) { operations += (occurrences - x.first); } // Else you can remove all the // occurrences of the number or // add the number sometimes until // the occurrences of the number are // not equal to the number itself so // you have to take the minimum of // all the occurrences else if (occurrences < x.first) { operations += min(occurrences, x.first - occurrences); } } // Return the operations return operations;}// Driver codeint main(){ int N = 6; vector<int> arr = { 3, 3, 5, 3, 2, 4 }; // Function call cout << minOperations(N, arr) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.HashMap;import java.util.Map; class GFG {// Function to find out minimum// number of operationstatic int minOperations(int N, int a[]){ // Map for storing frequency // of the array elements HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for(int i = 0; i < N; i++){ if(mp.containsKey(a[i])){ mp.put(a[i], mp.get(a[i]) + 1); } else{ mp.put(a[i], 1); } } // Variable to store the answer int operations = 0; int occurrences = 0; for (Map.Entry<Integer, Integer> x : mp.entrySet()){ occurrences = x.getValue(); // If the occurrence is greater // than number then the greedy // move is to remove extra occurrences if (occurrences > x.getKey()) { operations += (occurrences - x.getKey()); } // Else you can remove all the // occurrences of the number or // add the number sometimes until // the occurrences of the number are // not equal to the number itself so // you have to take the minimum of // all the occurrences else if (occurrences < x.getKey()) { operations += Math.min(occurrences, x.getKey() - occurrences); } } // Return the operations return operations;}// Driver code public static void main (String[] args) { int N = 6; int arr[] = { 3, 3, 5, 3, 2, 4 }; // Function call System.out.print(minOperations(N, arr)); }} |
Python3
# Python3 code to implement the above approachfrom collections import Counter# function to calculate the no of operationsdef minOperations(N, a): # a dictionary that stores the frequencies mp = dict(Counter(a)) # variable to store the operations operations = 0 # if occurrence > x, then the greedy move is # to remove extra occurrences for x in mp: occurrences = mp[x] if occurrences > x: operations += occurrences - x # else, you can remove all the occurrences of the no # or add x until the occurrences # of x are not equal to x itself. elif occurrences < x: operations += min(occurrences, x - occurrences) # return the operations return operations # Driver CodeN = 6arr = [3, 3, 5, 3, 2, 4]print(minOperations(N, arr))# This code is contributed by phasing17 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { // Function to find out minimum // number of operation static int minOperations(int N, int[] a) { // Map for storing frequency // of the array elements Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < a.Length; i++) { if (mp.ContainsKey(a[i])) { mp[a[i]] = mp[a[i]] + 1; } else { mp.Add(a[i], 1); } } // Variable to store the answer int operations = 0; foreach(KeyValuePair<int, int> x in mp) { int occurrences = x.Value; // If the occurrence is greater // than number then the greedy // move is to remove extra occurrences if (occurrences > x.Key) { operations += (occurrences - x.Key); } // Else you can remove all the // occurrences of the number or // add the number sometimes until // the occurrences of the number are // not equal to the number itself so // you have to take the minimum of // all the occurrences else if (occurrences < x.Key) { operations += Math.Min(occurrences, x.Key - occurrences); } } // Return the operations return operations; } // Driver code public static void Main() { int N = 6; int[] arr = { 3, 3, 5, 3, 2, 4 }; // Function call Console.Write(minOperations(N, arr)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code to implement the approach // Function to find out minimum // number of operation const minOperations = (N, a) => { // Map for storing frequency // of the array elements let mp = {}; for (let x in a) { mp[a[x]] = a[x] in mp ? mp[a[x]] + 1 : 1; } // Variable to store the answer let operations = 0; for (let x in mp) { let occurrences = mp[x]; // If the occurrence is greater // than number then the greedy // move is to remove extra occurrences if (occurrences > x) { operations += (occurrences - x); } // Else you can remove all the // occurrences of the number or // add the number sometimes until // the occurrences of the number are // not equal to the number itself so // you have to take the minimum of // all the occurrences else if (occurrences < x) { operations += Math.min(occurrences, x - occurrences); } } // Return the operations return operations; } // Driver code let N = 6; let arr = [3, 3, 5, 3, 2, 4]; // Function call document.write(minOperations(N, arr));// This code is contributed by rakeshsahni</script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
