0
$\begingroup$

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;

$\endgroup$

1 Answer 1

1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.