Given a list of $n$ integers. In one move we can either decrease exactly one element by $1,2$ or $5$. What is the minimum number of moves required to equalize the list?

For example: If the list is $2,2,3,7$ then we require at-least $2$ moves to equalize this array.

  1. Decreasing the third element by $1$ to get $2,2,2,7$
  2. Decreasing the fifth element by $5$ to get $2,2,2,2$

What could be the general approach to solve this problem?


While any entry exceeds the minimal entry by at least $5$, decrease it greadily by $5$. After that, all entries are $\in\{n,n+1,n+2,n+3,n+4\}$. If $n$ is the smallest original list entry, this step takes $\lfloor \frac{k-n}5\rfloor$ steps for an entry of value $k$.

You could now take $n$ as target minimum. That takes one additional move per $n+1$ and $n+2$, but two additional moves per $n+3$ and $n+4$. Thus if you have $a_k$ entries $n+k$, the cost is $$\tag1a_1+a_2+2a_3+2a_4. $$ Alternatively, you can take $n-1$ as target minimum. Then you need one move per $n$, $n+1$, and $n+4$ entry, but two moves per $n+2$ or $n+3$. So now the cost is $$\tag2 a_0+a_1+2a_2+2a_3+a_4.$$ If $a_0+a_2\le a_4$, this is better. Alternatively, you can take $n-2$ as target minimum, with cost $$\tag4a_0+2a_1+2a_2+a_3+2a_4.$$ Trying $n-3$ or less is not worth while as the cost would always beat least as big as the value given in $(1)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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