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

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

Kaeden Lara

Beginner2022-11-15Added 23 answers

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 + n I
where n is an integer. It means A and A + n I 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.
Kayden Mills

Kayden Mills

Beginner2022-11-16Added 2 answers

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 kth move of sequence S decrements the integer in position i, the kth move of sequence S increments all integers except the one in position i.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?