CODEWITHSUNDEEP
arraysalgorithm
user4090410
user4090410

Reputation:

Transform an array to another array by shifting value to adjacent element

I am given 2 arrays, Input and Output Array. The goal is to transform the input array to output array by performing shifting of 1 value in a given step to its adjacent element. Eg: Input array is [0,0,8,0,0] and Output array is [2,0,4,0,2]. Here 1st step would be [0,1,7,0,0] and 2nd step would be [0,1,6,1,0] and so on.

What can be the algorithm to do this efficiently? I was thinking of performing BFS but then we have to do BFS from each element and this can be exponential. Can anyone suggest solution for this problem?

Upvotes: 7

Views: 357

Answers (4)

v78
v78

Reputation: 2933

A simple greedy algorithm will work and do the job in minimum number of steps. The function returns the total numbers of steps required for the task.

int shift(std::vector<int>& a,std::vector<int>& b){

    int n = a.size();

    int sum1=0,sum2=0;
    for (int i = 0; i < n; ++i){
        sum1+=a[i];
        sum2+=b[i];
    }

    if (sum1!=sum2)
    {
        return -1;
    }

    int operations=0;
    int j=0;
    for (int i = 0; i < n;)
    {
        if (a[i]<b[i])
        {
            while(j<n and a[j]==0){
                j++;
            }
            if(a[j]<b[i]-a[i]){
                operations+=(j-i)*a[j];
                a[i]+=a[j];
                a[j]=0;
            }else{
                operations+=(j-i)*(b[i]-a[i]);
                a[j]-=(b[i]-a[i]);
                a[i]=b[i];
            }
        }else if (a[i]>b[i])
        {
            a[i+1]+=(a[i]-b[i]);
            operations+=(a[i]-b[i]);
            a[i]=b[i];
        }else{
            i++;
        }
    }

    return operations;
}

Here -1 is a special value meaning that given array cannot be converted to desired one.

Time Complexity: O(n).

Upvotes: 1

yeoman
yeoman

Reputation: 1681

void transform(int[] in, int[] out, int size)
{
    int[] state = in.clone();

    report(state);

    while (true)
    {
        int minPressure = 0;
        int indexOfMinPressure = 0;

        int maxPressure = 0;
        int indexOfMaxPressure = 0;

        int pressureSum = 0;

        for (int index = 0; index < size - 1; ++index)
        {
            int lhsDiff = state[index] - out[index];
            int rhsDiff = state[index + 1] - out[index + 1];

            int pressure = lhsDiff - rhsDiff;

            if (pressure < minPressure)
            {
                minPressure = pressure;
                indexOfMinPressure = index;
            }

            if (pressure > maxPressure)
            {
                maxPressure = pressure;
                indexOfMaxPressure = index;
            }

            pressureSum += pressure;
        }

        if (minPressure == 0 && maxPressure == 0)
        {
            break;
        }

        boolean shiftLeft;

        if (Math.abs(minPressure) > Math.abs(maxPressure))
        {
            shiftLeft = true;
        }
        else if (Math.abs(minPressure) < Math.abs(maxPressure))
        {
            shiftLeft = false;
        }
        else
        {
            shiftLeft = (pressureSum < 0);
        }

        if (shiftLeft)
        {
            ++state[indexOfMinPressure];
            --state[indexOfMinPressure + 1];
        }
        else
        {
            --state[indexOfMaxPressure];
            ++state[indexOfMaxPressure + 1];
        }

        report(state);
    }
}

Upvotes: 1

Ian Mercer
Ian Mercer

Reputation: 39277

I think you can do this simply by scanning in each direction tracking the cumulative value (in that direction) in the current array and the desired output array and pushing values along ahead of you as necessary:

scan from the left looking for first cell where
  cumulative value > cumulative value in desired output
while that holds move 1 from that cell to the next cell to the right 

scan from the right looking for first cell where
  cumulative value > cumulative value in desired output
while that holds move 1 from that cell to the next cell to the left

For your example the steps would be:

FWD: [0,0,8,0,0] [0,0,7,1,0] [0,0,6,2,0] [0,0,6,1,1] [0,0,6,0,2]

REV: [0,1,5,0,2] [0,2,4,0,2] [1,1,4,0,2] [2,0,4,0,2]

Upvotes: 2

yd1
yd1

Reputation: 277

i think BFS could actually work.

notice that n*O(n+m) = O(n^2+nm) and therefore not exponential.

also you could use: Floyd-Warshall algorithm and Johnson’s algorithm, with a weight of 1 for a "flat" graph, or even connect the vertices in a new way by their actual distance and potentially save some iterations.

hope it helped :)

Upvotes: 1

Related Questions