Alex Rivera | Logout

What is the more efficient algorithm to equalize a vector?

Asked 2011-06-12T20:38:44.603
10

Given a vector of n elements of type integer, what is the more efficient algorithm that produce the minimum number of transformation step resulting in a vector that have all its elements equals, knowing that :

  • in a single step, you could transfer at most one point from element to its neighbours ([0, 3, 0] -> [1, 2, 0] is ok but not [0, 3, 0] -> [1, 1, 1]).
  • in a single step, an element could receive 2 points : one from its left neighbour and one from the right ([3, 0 , 3] -> [2, 2, 2]).
  • first element and last element have only one neighbour, respectively, the 2nd element and the n-1 element.
  • an element cannot be negative at any step.

Examples :

Given :
 0, 3, 0
Then 2 steps are required :
 1, 2, 0
 1, 1, 1

Given :
 3, 0, 3
Then 1 step is required :
 2, 2, 2

Given :
 4, 0, 0, 0, 4, 0, 0, 0
Then 3 steps are required :
 3, 1, 0, 0, 3, 1, 0, 0
 2, 1, 1, 0, 2, 1, 1, 0
 1, 1, 1; 1, 1, 1, 1, 1

My current algorithm is based on the sums of the integers at each side of an element. But I'm not sure if it produce the minimum steps.

FYI the problem is part of a code contest (created by Criteo http://codeofduty.criteo.com) that is over.

algorithm performance
Edit
Report

1 Answer

6

Here is a way. You know the sum of the array, so you know the target number in each cell. Thus you also know the target sum for each subarray. Then iterate through the array and on each step you make a desicion:

  1. Move 1 to the left: if the sum up to the previous element is less then desired.
  2. Move 1 to the right: if the sum up to the current element is more than desired
  3. Don't do anything: if both of the above are false

Repeat this until no more changes are made (i.e. you only applied 3 for each of the elements).

    public static int F(int[] ar)
    {
        int iter = -1;
        bool finished = false;
        int total = ar.Sum();

        if (ar.Length == 0 || total % ar.Length != 0) return 0; //can't do it
        int target = total / ar.Length;

        int sum = 0;

        while (!finished)
        {
            iter++;
            finished = true;
            bool canMoveNext = true;

            //first element
            if (ar[0] > target)
            {
                finished = false;
                ar[0]--;
                ar[1]++;

                canMoveNext = ar[1] != 1;
            }

            sum = ar[0];
            for (int i = 1; i < ar.Length; i++)
            {
                if (!canMoveNext)
                {
                    canMoveNext = true;
                    sum += ar[i];
                    continue;
                }

                if (sum < i * target && ar[i] > 0)
                {
                    finished = false;
                    ar[i]--;
                    ar[i - 1]++;
                    sum++;
                }
                else if (sum + ar[i] > (i + 1) * target && ar[i] > 0) //this can't happen for the last element so we are safe
                {
                    finished = false;
                    ar[i]--;
                    ar[i + 1]++;

                    canMoveNext = ar[i + 1] != 1;
answered 2011-06-12T21:39:40.347

Your Answer