Equal-element array transformation problem

equal_element_array_transformation.py

#!/usr/bin/env python

"""Problem Description:

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 detailed as follows:

    Each element has to be incremented or decremented by 1 in a single step

The question is: find the minimum number of steps 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).
"""

def print_step(steps, step, A):

    print "step %(steps)s: %(step)s; and array is transformed to %(A)s" % { 
                                                                            "steps": str(steps),
                                                                            "step" : step,
                                                                            "A"    : A
                                                                          }

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 an equalizer ==> O(N) operation

    If convergence succeeds, then return the maximum distance/minum # of steps 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))

def is_equalizer(A, m):
    for e in A:
        if e != m:
            return False
    return True

def run_steps(A, m, max_dis):

    C = [e for e in A]

    if converges(C, m, max_dis) != -1:
        steps, step = 0, []

        while not is_equalizer(C, m):
            steps += 1
            for i in xrange(len(C)):
                if C[i] > m:
                    C[i] -= 1
                    step.append(-1)
                elif C[i] < m:
                    C[i] += 1
                    step.append(1)
                else: # C[i] == m; start oscillating
                    C[i] += 1
                    step.append(1)
            print_step(steps, step, C)
            del step[:]

        return steps

def transform(A):
    """Transform A into a list of equal elements. Print out intermediate steps. Time complexity is O(N^2)
    """

    if not A:
        return -1

    return run_steps(A, *middle_and_mnos(A))

if __name__ == "__main__":

    inputs = [
        [],
        [2],
        [3,3,3,3,3],
        [11, 3, 7, 1],
        [1, 7, 3, 7, -1, 11, 9],
        [1, 1, -1, 1, -1, 9, 15,7]
    ]

    # if want to see intermediate steps, use transform() !
    # if only want to know minimum # of steps, O(N) solution exists: using find_minsteps()!
    for A in inputs:
        print
        print "Input array is: %s" % A
        print "Minimum # of steps is %s steps" % transform(A)
        # print "Array", A, "needs ", find_minsteps(A), "steps to transform."