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 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.