# minimum insertions and deletions required to ensure that each value X occurs X times

I would like to brainstorm/get some advice/tips regarding the following question. Given an array,you can either insert elements or you can delete elements from it.Note the insertion/deletion must be done in such a way so that in the end,for any element X in the array,X occurs X times. The objective is to find the minimum no of moves you can make to achieve the desired result. For example if A is [1,1,3,4,4,4].Then we can delete one occurence of 1 and 3 respectively and add a 4 to give us [1,4,4,4,4].In the final array 1 occurs 1 time and 4 occurs 4 times.Answer is 3 Again if A is [10,10,10].Then you can simply remove all 10s to get 0.So the answer here is 3. One way of doing is to have a map that keeps track of how many times each value occurs. After this I tried using the approach mentioned in the below link(but it only handles deletions and not insertion) So I would like some tips on how to approach this problem while taking care of both insertion and deletions. ''' unordered map<int, int> map;

Your approach seems good. Here is a high level description of the algorithm to solve this question:

1. Build a hashmap from the values in the array $$A$$ to the number of occurrences they have in that array. This can be done in $$O(n)$$, simply by going through $$A$$ and incrementing the count by $$1$$ for every element you see.

2. Start keeping track of the number of required insertion \ deletion operations. For simplicity, lets store it in a variable named $$cnt$$.

3. For every element $$k$$ in the hashmap, denote by $$v(k)$$ the number of occurrences it has in $$A$$. Then, do the following:

• Do $$cnt\leftarrow cnt + \min(|v(k)-k|,v(k))$$
4. Return the value of $$cnt$$

Basically, the algorithm tries to check for every value $$k$$ in $$A$$ which requires the least operations:

1. Inserting or deleting until there are $$k$$ copies of $$k$$: This will require $$|v(k)-k|$$ operations since there are currently $$v(k)$$ copies and we need exactly $$k$$ copies
2. Deleting until there aren't copies at all. This is the case in the example of the array $$A=[10,10,10]$$. In this case, we need $$v(k)$$ operations to delete all copies.

Those two cases cover all things we can do to make the array $$A$$ into a "correct" form. We will "fix" $$A$$ for a specific value $$k$$ by doing the case that requires the least operations, and hence we can calculate the number of required operations to "fix" a certain $$k$$ is: $$\min(|v(k)-k|,v(k))$$. Sum this up over all $$k$$'s, and you got yourself the answer!