Minimize shifting half of each element to either sides to reduce Array

Given an array arr[] of size Nthe task is to find the minimum number of steps required to reduce all Array elements to 0 except the first and last, where in each step:

  • Choose any index i (0decrement the element at that index (arr[i]) by 2
  • Then increment any two elements, arr[j]where 0<=j

If it is not possible to reduce the given array as desired, return -1.

Input: arr[] = {2, 3, 3, 4, 7}
Output: 6
Explanation: Consider the below steps as how the reduction will be done

steps array
0 {2, 3, 3, 4, 7} original array
1 {2, 4, 1, 4, 8} deduct 2 from a[2] add it to a[1] and a[4]
2 {3, 2, 2, 4, 8} deduct 2 from a[1] add it to a[0] and a[2]
3 {4, 0, 2, 4, 9} deduct 2 from a[1] add it to a[0] and a[4]
4 {5, 0, 0, 4, 10} deduct 2 from a[2] add it to a[0] and a[4]
5 {6, 0, 0, 2, 11} deduct 2 from a[3] add it to a[0] and a[4]
6 {7, 0, 0, 0, 12} deduct 2 from a[3] add it to a[0] and a[4]

Input: arr[] = {3,2,1,3,5,4}
Output: 7

Approach:

Intuition: The above problem can be solved with the help of below observations:

  • Case 1: A[i] is even
    • As we always subtract 2 from a[i]this means a[i] must be an even numberelse after subtracting 2 certain number of times, 1 will remain on which no operation can be performed any further.
  • Case 2: A[i] is odd
    • So to make every element 0, we need to have even numbers, and if we do not have even numbers then we have to make it even.
    • When we subtract 2 from a[i]we select i such that arr[i] is even and arr[j] and/or arr[k] are odd.
    • So adding 1 to them will make then an even number.
  • Case 3: If there is no odd element
    • If we do not have any odd number, then we can choose the first and last elements, and directly add 1 to a[0] and a[n-1] As we don’t have to reduce these elements.

Illustration 1:

Suppose we have {3,2,1,3,5,4},

Step 1: There is an odd element in the array. So choose the 1st odd element in index range (0, N-1), ie a[2] = 1
We take 2 from a[1] add 1 to a[0] and 1 to a[2].

So the array becomes {4, 0, 2, 3, 5, 4}, and our 1 becomes 2, which is now an even number.

Step 2: Now consider next odd number in range (0, N-1), ie a[3] = 3
We take 2 from a[2] add 1 to a[0] and 1 to a[2].

So the array becomes {5, 0, 0, 4, 5, 4}, and our 3 becomes 4, which is now an even number.

Step 3: Now consider next odd number in range (0, N-1), ie a[4] = 5
We take 2 from a[3] add 1 to a[0] and 1 to a[4].

So the array becomes {6, 0, 0, 2, 6, 4}, and our 5 becomes 6, which is now an even number.

Step 4 – 7: We take 2 from each even numbers ie, 2 and 6 and shift it to a[0] and a[n-1]
As at each step we can reduce by 2, So we will require 1 step for element 2 and 3 steps for element 6.

Therefore the total operations become 7 and finally the array becomes {10, 0, 0, 0, 0, 8}.

Illustration 2:

Now if we only have 3 elements and the middle value is an odd number,
Then answer is not possible because the only possible selection is j=0,i=1 and k=2.

So after subtracting 2 a certain number of times a[i] will become 1.

So in this case a valid answer is not possible, and the answer will be -1.

Below is the implementation :

C++

#include <bits/stdc++.h>

using namespace std;

 

int stepsToRearrange(vector<int>& A, int n)

{

    

    

    

    if (n == 3 && (A[1] % 2 == 1))

        return -1;

 

    int steps = 0, countOne = 0;

 

    

    

    

    

    for (int i = 1; i < n - 1; i++) {

        steps += (A[i] + 1) / 2;

        countOne += (A[i] == 1);

    }

 

    

    

    if (countOne == n - 2)

        return -1;

 

    

    return steps;

}

 

int main()

{

    vector<int> arr = { 3, 2, 1, 3, 5, 4 };

    int N = sizeof(arr) / sizeof(arr[0]);

 

    cout << stepsToRearrange(arr, N);

 

    return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Leave a Comment