CODEWITHSUNDEEP
algorithmdata-structures
Shobhit Chaturvedi
Shobhit Chaturvedi

Reputation: 13

find minimum number of moves to make all elements of array equal to 0

I have a array A = {-8,-5,0,-3,8,8,2,-2} ,i want to calculate minimum number of moves requires to make all elements of array 0 using array elements only,given the following condition-->

1.an element at index x can be moved directly to either x+1,x+2 position or x-1, x-2 position in a single move,after that move count will increase.

  1. no element can be moved before start index of array i.e. 0 and after end index i.e. length of array.

e.g. in array above minimum move will be 31 :

  1. all 8 elements at index 4 can be moved to index 0 in total 16 moves (because all 8 elements requires 2 moves). moves:16.
  2. 3 elements from index 5 can be moved to index 3 in 3 moves(3 elements take 1 move each) and remaining 5 elements from index 5 can be moved to index 2 in 10 moves (5 elements require 2 moves each so 10 moves total). moves = 16+3+10 = 29.
  3. 2 elements from index 6 moves to index 7 in 2 moves(1 move each) . moves = 29+2 = 31 .

take another example for input array {-1,-1,0,1,1} ,optimal solution gives answer 3 as follows--> 1 from index 3 moves to index 1 in 1 move, then 1 from index 4 moves to index 0 in 2 moves , so total moves will be 3.

i tried writing code in c++ but dint get optimal solution ,also not able to cover all scenarios .

below is my code but not in working condition 

int solution1(vector < int > & c) {

  int alen = c.size();
  if (alen == 0) return -1;

  int move = 0;
  int moved = 0;
  for (int j = 0; j < alen; ++j) {
    if (c[j] < 0) {
      for (int k = j + 1; k < alen; ++k) {
        moved = 0;
        if (c[k] > 0) {
          c[j] = 0 - c[j];
          if (c[j] <= c[k]) {
            c[k] = c[k] - c[j];
            moved = c[j];
            c[j] = 0;
          } else {
            c[j] = c[k] - c[j];
            moved = c[k];
            c[k] = 0;
          }
          if (k - j >= 2) {
            if ((k - j) % 2)
              move += ((k - j + 1) / 2) * moved;
            else
              move += ((k - j) / 2) * moved;
          } else {
            move += moved;
          }
          if (c[j] == 0) break;
        }
      }
    } else if (c[j] > 0) {
      for (int kk = j + 1; kk < alen; ++kk) {
        moved = 0;
        if (c[kk] < 0) {
          c[kk] = 0 - c[kk];
          if (c[j] <= c[kk]) {
            c[kk] = c[j] - c[kk];
            moved = c[j];
            c[j] = 0;
          } else {
            c[j] = c[j] - c[kk];
            moved = c[kk];
            c[kk] = 0;
          }
          if (kk - j >= 2) {
            move += ((kk - j) / 2) * moved;
          } else {
            move += moved;
          }
          if (c[j] == 0) break;

        }
      }
    }

  }
  if (move > 0) return move;
  else return -1;
}

Upvotes: 0

Views: 3169

Answers (1)

Nilesh
Nilesh

Reputation: 1343

The given problem requires a constructive solution. Since the span of a move extends to (x - 2, x + 2) we maintain an overhead array of size 2 which maintains the cost of moving elements as we go from i to (i + 1)th position for the even and odd indices. We iterate over the given array from left-to-right and calculate the cost of moving all the elements which are still left, to the left of the index i. Such a cost can be calculated using the overhead array (refer code below). If at any step there exists a possibility of cancelling out some negative integers with positive integers, we pick up those elements first which were going to cost us +1 if he had moved from i to (i + 1) in our next move for the neutralising process.

The point of observation is that if we keep moving an element at index x from left-to-right it'll only add to the cost of the moves at points (x + 1), (x + 3), (x + 5), ... and so on. Here's a running code for the same: https://ideone.com/TFunNG

int solve(vector<int> v) {
    vector<int> overhead(2,0);
    int num_of_moves = 0, sum = 0;
    for(int i = 0; i < v.size(); i++) {
        num_of_moves += overhead[i % 2];
        int left = abs(v[i]);
        if((sum > 0 && v[i] < 0) || (sum < 0 && v[i] > 0)) {
            int used = min(abs(sum), abs(v[i]));
            int diff = min(overhead[(i + 1) % 2], used);
            overhead[(i + 1) % 2] -= diff;
            overhead[i % 2] -= min(overhead[i % 2], (used - diff));
            left -= used;
        }
        sum += v[i];
        overhead[(i + 1) % 2] += abs(left);
    }

    assert(sum == 0);
    return num_of_moves;
}

The overall runtime complexity of the solution is O(n).

Upvotes: 1

Related Questions