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$ 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?

share|improve this question
add comment

1 Answer

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\}$.

share|improve this answer
    
+1 Nice answer. –  user1551 Jan 1 '13 at 14:25
add comment

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.