No of transformation steps to qualize array

Hi Can any one tell me how to solve this problem in C#. I have an array consisting of N elements. elements in array can be positive and negative intgers. if A=[11, 3, 7, 1] i want to calculate minimum no of transformation steps required to make array elements equal. each element in array can be incremented or decremented by 1.

Array A will need 5 transformation steps to get A =[6, 6, 6, 6]

In very transformation each element has to be incremented or decremented by 1.

[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)

Some in some arrays it may not be possible.

for example it is not possible with [1,4,7] to equalise elements to on开发者_运维知识库e number. In Such cases it should return -1

Thanks in advance.

Well presumably you just:

• Find the maximum element
• Find the minimum element
• The number of steps required will be half the difference between the maximum and the minimum, rounding up

You'd find the mean of the maximum and minimum element, rounding either up or down - it won't affect the number of steps - and then on each transformation step, you'd adjust each array element towards that mean.

EDIT: It's hard to see how you could get more efficient than this. In each step, the maxmimum and minimum elements can't get more than 2 closer to each other (the maximum being reduced by one, the minimum being increased by one) so the number of steps is at least half the difference, rounding up. My solution also says how you get to that state in exactly half the difference, rounding up, so it's a concrete solution, with none better.

EDIT: Here's the code to perform the transformations. Not as efficient as it can be, but it works...

using System;
using System.Linq;

class Test
{
    static void Main()
    {
        int[] current = new[] { 1, 3, 9, 11, 5 };

        // Check all odd or all even    
        if (current.Select(x => x % 2).Distinct().Skip(1).Any())
        {
            Console.WriteLine("No solution!");
            return;
        }

        while (current != null)
        {
            Console.WriteLine(string.Join(" ", current));
            current = Transform(current);
        }
    }

    static int[] Transform(int[] input)
    {
        // We could do the "mean" calculation just once,
        // but it doesn't really matter for the sake of
        // demonstration
        int max = input.Max();
        int min = input.Min();
        if (max == min)
        {
            // Done
            return null;
        }

        int mean = (max + min) / 2;
        return input.Select(x => x > mean ? x - 1 : x + 1)
                    .ToArray();
    }
}

Does this work?

edit sorry, this:

public int[] Equalize(int[] arr)
{
        int min = int.MaxValue;
        int max = int.MinValue;
        int parity = arr[0] % 2;
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] % 2 != parity) return null;
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }
        int diff = (max - min) / 2;            
        int midVal = diff + min;
        return arr.Select(i => midVal).ToArray();
}

Is ROUND_DOWN(SUM(each) / N) works as expected?

Java 8 version of Jon Skeet solution

public static void main(String[] args) throws FileNotFoundException {

         System.out.println(getTransformationCount(new int[] {1, 3, 9, 11, 5 }));

    }

    public static int getTransformationCount(int[] A) {

        int count = 0;
        A = Transform(A);

        if (IntStream.of(A).map(n -> n % 2).distinct().skip(1).count() > 0) {
            return -1;
        }

        while (A != null) {
            A = Transform(A);
            count++;
        }
        return count;
    }

    public static int[] Transform(int[] input) {

        int min = Arrays.stream(input).max().getAsInt();
        int max = Arrays.stream(input).min().getAsInt();
        if (max == min) {
            return null;
        }

        int mean = (max + min) / 2;

        return Arrays.stream(input).map((n) -> {
            if (n > mean)
                return n - 1;
            else
                return n + 1;

        }).toArray();
    }