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?
sbrigynt7b
Answered question
2022-11-14
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 & Explanation
Kaeden Lara
Beginner2022-11-15Added 23 answers
Just pay attention what matters is the relative differences between elements of an array. If is an array, and is the array of all ones, then from this problem's point of view
where is an integer. It means and are equivalent. If you look at the first operation in another way, you might see both algorithms are equivalent. Instead of taking unit off elements, add to all the elements of the array and subtract 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.
Kayden Mills
Beginner2022-11-16Added 2 answers
Show that if there is a sequence of "moves" that make all the integers equal, where each move decrements a single integer by , there is a sequence of moves that make all the integers equal where each move increments integers by . In particular, you derive the sequence from the sequence very simply: if the th move of sequence decrements the integer in position , the th move of sequence increments all integers except the one in position .