Emmanuel Wilson
2 min readMar 9, 2022

--

Nice solution Leo!
Btw, I noticed an interesting pattern in this problem.
I will define some parameters first.

Let:
M = Min. element in the array.
S = Sum of all elements in the array.
N = Number of elements in the array.

I believe that the question is asking for the Minimum moves require to make the array elements equal. This is because the moves requires to make the array elements equal is not unique.

With that in mind, let's take K to be the number of moves required to make the arrays elements equal.

Observations:
1. Notice that each move will increase the sum, S by (N-1). This means that after K moves (when the elements are equal), the total sum will be become
S + (N-1)*K.

2. Notice also (from your table) that the min element in the given array M, only increased by K when the array elements become equal (i.e. M becomes M+K). We also know that all the elements will be equal too. Thus, sum of the N elements will be
(M+K)*N.

Equating the expressions in Observations 1 and 2,

(M+K)*N = S + (N-1) * K
==> MN + KN = S + NK - K
==> MN = S - K
==> K = S - MN <----- Answer

So, to find K, you will only have to iterate the array once to get the min element, M, and also calculate the sum of all elements S. The number of elements in the array is N, which is already known.

This will only take O(N) time and O(1) space.

--

--

Emmanuel Wilson

Software Engineer | Competitive Programmer | Graduate Student in SE & Data Analysis | Music freak :-) I write about tech and problem solving