Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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