Prove that incrementing n - 1 numbers is the same as decrementing 1

Question

I ran into a programming problem that goes something like this:

Given a non-empty integer array of size n, find the minimum number of moves it takes to make all the integers equal, where a move means incrementing n-1 integers by 1.

It turns out that incrementing n-1 numbers has the "same effect" as decrementing a single number. By "same effect", I mean it takes the same number of steps to make all the integers equal. Basically, I find the minimum element and return the sum of differences for all the integers in the array.

However, I could not prove that this was the case. I got the correct answer but it was more of a guess. How can a proof be constructed to show that the two strategies would take the same number of steps?

Answer 1

Just pay attention what matters is the relative differences between elements of an array. If $A$ is an array, and $I$ is the array of all ones, then from this problem's point of view

$A= A+nI$

where $n$ is an integer. It means $A$ and $A+nI$ are equivalent.

If you look at the first operation in another way, you might see both algorithms are equivalent. Instead of taking $1$ unit off $n-1$ elements, add $1$ to all the elements of the array and subtract $1$ from only one element. This algorithm is the same as the second algorithm. It keeps the relative difference between elements, but they are a shifted version of what is done in the second algorithm. So, if you find an optimum sequence of operations for one algorithm, then the same sequence is applicable to the other algorithm.

Answer 2

Show that if there is a sequence $S$ of $M$ "moves" that make all the integers equal, where each move decrements a single integer by $1$, there is a sequence $S'$ of $M$ moves that make all the integers equal where each move increments $n-1$ integers by $1$.

In particular, you derive the sequence $S'$ from the sequence $S$ very simply: if the $k$th move of sequence $S$ decrements the integer in position $i$, the $k$th move of sequence $S'$ increments all integers except the one in position $i$.

Answer 3

Let $I_{max}$ be the maximum number in the array. Define a numbering system base $B=10^{\alpha}$,
Where $\alpha$ is the minimum integer satisfy {$10^{\alpha} \gt (I_{max}+1)$}. i.e. $$ \quad I_{max}=7 \Rightarrow B=10\space\,,\quad I_{max}=35 \Rightarrow B=100\space\,,\space\cdots\space\text{etc} $$ Encode all array elements in a single number $(x)$ base $(B)$ as follow: $$ x = I_{n}\cdot B^{n}+I_{n-1}\cdot B^{n-1}+I_{n-2}\cdot B^{n-2}+\cdots+I_{1}\cdot B^{1}+I_{0}\cdot B^{0} $$ We notice that if we increase all elements by $1$, this is equal to not effecting anything at all!
As you know, we call this the Neutral effect. i.e. $\{3,2,2,1\} = \{4,3,3,2\} = \{2,1,1,0\}$.
Thus, the Neutral Elements (Identity Elements) of the system is:
$$ I = 1\cdot B^{n}+1\cdot B^{n-1}+\cdots+1\cdot B^{1}+1\cdot B^{0} = B^{n}+B^{n-1}+\cdots+B^{1}+B^{0} \Rightarrow \\ x = x + I = x + B^{n}+B^{n-1}+\cdots+B^{1}+B^{0} \Rightarrow \color{red}{x + (B^{n-1}+\cdots+B^{1}+B^{0}) = x - B^{n}} $$ Which means the effect of adding "ONE" (n-1) times is equal to subtract “ONE” one time.