Convert an array to another array by shifting the value to a neighboring element

Question

I have been given 2 arrays, Input and Output Array. The goal is to convert the input array to the output array by performing an offset of 1 value at this step by an adjacent element. For example: the input array is [0,0,8,0,0], and the output array is [2,0,4,0,2]. Here, the first step will be [0,1,7,0,0], and the second step will be [0,1,6,1,0] and so on.

What could be the algorithm for this? I was thinking about doing BFS, but then we have to do BFS from each element, and this can be exponential. Can anyone suggest a solution to this problem?

Answer 1

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 the values ​​forward as needed:

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 

As an example, follow these steps:

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]

Answer 2

A simple greedy algorithm will work and do the job with as few steps as possible. The function returns the total number 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+=(ji)*a[j]; a[i]+=a[j]; a[j]=0; }else{ operations+=(ji)*(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 the given array cannot be converted to the desired one.

Difficulty of time: O (n).

Answer 3

I think BFS really can work.

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

you can also use the Floyd-Warsall algorithm and the Johnson algorithm, with a weight of 1 for a “flat” graph, or even connect the vertices in a new way with their actual distance and potentially save some iterations.

hope this helped :)

Answer 4

 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); } }