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

Question

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;

Answer 1

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!