Minimize shifting half of each element to either sides to reduce Array
Given an array arr[] of size N, the task is to find 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 (0<i<N-1) and decrement the element at that index (arr[i]) by 2
- Then increment any two elements, arr[j], where 0<=j<i and arr[k], where i<k<n, by 1.
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 donesteps 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 number, else 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), i.e. 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), i.e. 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), i.e. 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 i.e, 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++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to shift the array int stepsToRearrange(vector< int >& A, int n) { // if A has 3 elements and // 2nd element is odd then // answer is not possible if (n == 3 && (A[1] % 2 == 1)) return -1; int steps = 0, countOne = 0; // Select even numbers and subtract 2 // Now for the odd number // we add one and make them even. // so total steps = (a[i]+1)/2 for ( int i = 1; i < n - 1; i++) { steps += (A[i] + 1) / 2; countOne += (A[i] == 1); } // If all numbers in index 1 to n-2 = 1 // then answer is not possible if (countOne == n - 2) return -1; // return steps return steps; } // Driver Code int main() { vector< int > arr = { 3, 2, 1, 3, 5, 4 }; int N = sizeof (arr) / sizeof (arr[0]); cout << stepsToRearrange(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to shift the array public static int stepsToRearrange( int A[], int n) { // if A has 3 elements and // 2nd element is odd then // answer is not possible if (n == 3 && (A[ 1 ] % 2 == 1 )) return - 1 ; int steps = 0 , countOne = 0 ; // Select even numbers and subtract 2 // Now for the odd number // we add one and make them even. // so total steps = (a[i]+1)/2 for ( int i = 1 ; i < n - 1 ; i++) { steps += (A[i] + 1 ) / 2 ; if (A[i] == 1 ) { countOne += 1 ; } } // If all numbers in index 1 to n-2 = 1 // then answer is not possible if (countOne == n - 2 ) return - 1 ; // return steps return steps; } // Driver Code public static void main(String[] args) { int arr[] = { 3 , 2 , 1 , 3 , 5 , 4 }; int N = arr.length; System.out.print(stepsToRearrange(arr, N)); } } // This code is contributed by Taranpreet |
Python3
# python3 program for the above approach # Function to shift the array def stepsToRearrange(A, n): # if A has 3 elements and # 2nd element is odd then # answer is not possible if (n = = 3 and (A[ 1 ] % 2 = = 1 )): return - 1 steps, countOne = 0 , 0 # Select even numbers and subtract 2 # Now for the odd number # we add one and make them even. # so total steps = (a[i]+1)/2 for i in range ( 1 , n - 1 ): steps + = (A[i] + 1 ) / / 2 countOne + = (A[i] = = 1 ) # If all numbers in index 1 to n-2 = 1 # then answer is not possible if (countOne = = n - 2 ): return - 1 # return steps return steps # Driver Code if __name__ = = "__main__" : arr = [ 3 , 2 , 1 , 3 , 5 , 4 ] N = len (arr) print (stepsToRearrange(arr, N)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; class GFG { // Function to shift the array static int stepsToRearrange( int [] A, int n) { // if A has 3 elements and // 2nd element is odd then // answer is not possible if (n == 3 && (A[1] % 2 == 1)) return -1; int steps = 0, countOne = 0; // Select even numbers and subtract 2 // Now for the odd number // we add one and make them even. // so total steps = (a[i]+1)/2 for ( int i = 1; i < n - 1; i++) { steps += (A[i] + 1) / 2; if (A[i] == 1) { countOne += 1; } } // If all numbers in index 1 to n-2 = 1 // then answer is not possible if (countOne == n - 2) return -1; // return steps return steps; } // Driver Code public static void Main() { int [] arr = { 3, 2, 1, 3, 5, 4 }; int N = arr.Length; Console.Write(stepsToRearrange(arr, N)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for the above approach // Function to shift the array function stepsToRearrange(A, n) { // if A has 3 elements and // 2nd element is odd then // answer is not possible if (n == 3 && (A[1] % 2 == 1)) return -1; let steps = 0, countOne = 0; // Select even numbers and subtract 2 // Now for the odd number // we add one and make them even. // so total steps = (a[i]+1)/2 for (let i = 1; i < n - 1; i++) { steps += Math.floor((A[i] + 1) / 2); countOne += (A[i] == 1); } // If all numbers in index 1 to n-2 = 1 // then answer is not possible if (countOne == n - 2) return -1; // return steps return steps; } // Driver Code let arr = [ 3, 2, 1, 3, 5, 4 ]; let N = arr.length; document.write(stepsToRearrange(arr, N)); // This code is contributed by Samim Hossain Mondal. </script> |
7
Time Complexity: O(N)
Auxiliary Space: O(1)