Minimum number of transformation required to equalize a list

Question

Given a list of $n$ positive elements (including $0$). We are allowed to perform only one transformation which is to increment each element of the list except one. What are the minimum number of transformation required to equalize this list?

For example, $n = 3$ and the list being $1,2,3$. We need $3$ such transformation as $2,3,3 \to 3,3,4 \to 4,4,4$

For $n = 4$ and the list being $1,3,2,4$ the minimum number of transformation required is $6$

Some thoughts:

I implemented something like breadth first search to solve this one but due to it's unique nature the graph is growing large very fast making my solution taking too much time even for $n = 6$.

Which is the best approach to solve this?

Answer 1

Incrementing all but one element is essentially the same (for the purpose of equalizing all elements) as decreasing one element. But this gives us an obvious strategy: decrease all non-minimal elements until they equal the minimal element. Thus if you are given $a_1, a_2, \ldots, a_n$ we need exactly $$\sum_{k=1}^n a_k - n\cdot\min\{a_1,\ldots,a_n\}$$ steps. Or, if you like, this can be rewritten as $$\sum_{k=1}^n (a_k - a)$$ with $a:=\min\{a_1,\ldots,a_n\}$.