Consider this problem:

```
There is an array consisting of N elements, all the elements
are integer numbers (can be positive, zero or negative).
A transformation step is to be applied to the array,
which is as follows:
Each element HAS to be incremented or decremented by 1 in a
single step; Please find the minimum number of steps (MNOS)
required to transform the original array into an array with
all equal elements. If such array cannot be found, then return
-1.
For example:
[11, 3, 7, 1] (initial array)
[10, 4, 6, 2] (after step 1)
[9, 5, 7, 3] (after step 2)
[8, 6, 6, 4] (after step 3)
[7, 7, 5, 5] (after step 4)
[6, 6, 6, 6] (after step 5)
The required time complexity is O(N) and space complexity is O(1)
```

Not a difficult problem to tackle. Obviously, a minimum number of steps exists if a **middle number** can be found for
every element in the array to converges to. A middle number is an integer that is the mean of the largest and the smallest
numbers in the sequence (If the mean is not a whole number, then the sequence will not converge! Think about why?!).

Such middle number is chosen because the minimum number of steps (MNOS) is then capped by the distance between the middle
number and the largest or smallest number in the sequence, in fact, the distance is the smallest since the middle number is
the mean. In other words, this choice guarantees a candidate number which the sequence *might* converges to in **the least
necessary steps**. However, it still does not guarantee convergence.

To confirm if the sequence converges to the middle number, the **difference** between the distance of each element
and the distance of the largest or smallest element to the middle number has to be an even number.

The difference represents the **extra** MNOS for an element to reach the middle number **BEFORE** the largest (or smallest)
element does. All elements except the largest (or smallest) reach the middle number sooner than the largest (or smallest)
element since their distance(s) to the middle number are always shorter. Once they reach the middle number, they start to
*oscillate* around the middle number. No matter how they oscillate, they need *half* of the extra steps to oscillate AWAY
from the middle number, and the other half to return back; that’s why the extra MNOS has to be even, if not, then the element
does not converge to middle number, and therefore the sequence does not converge.

If all the extra MNOS are even, then the entire sequence *synchronizes* to reach the middle number at the same time - when the
largest (or smallest) element reaches the middle number.

Enough explanation, let’s see how it is implemented.

```
def minmax(A):
"""
Given an integer array A, return the min and max values
in the sequence => O(N)
"""
lo = hi = A[0]
for i in xrange(1, len(A)):
if A[i] > hi:
hi = A[i]
elif A[i] < lo:
lo = A[i]
return lo, hi
def middle_and_mnos(A):
"""
Given an integer array A, return the middle number and
the distance to the middle number => O(N)
"""
l, h = minmax(A)
m = (l+h)/2
d = h - m
return m, d
def converges(A, m, max_dis):
"""
Test if list A converges to the middle number => O(N)
If convergence succeeds, return the max distance/MNOS
to convergence! Otherwise return -1
"""
for e in A:
if (max_dis - abs(e-m)) % 2 != 0: return -1
return max_dis
def find_minsteps(A):
if not A:
return -1
return converges(A, *middle_and_mnos(A))
```

The worse case running time for the above implementation is O(2N), since it has to search the array twice to give a final answer, but the space complexity is indeed O(1). To see a implementation which also demonstrates the steps of transformation, please refer to this gist post.