text: # Minimize shifting half of each element to either sides to reduce Array
  
  Last Updated : 28 Mar, 2022
  
  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 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 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 ` `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
  
   ``
  
  Output
  
  `7`
  
  Time Complexity: O(N)
  Auxiliary Space: O(1)
  
  Article Tags :
  Practice Tags :
explanation: The document describes a problem involving an array and the task of reducing all elements to 0 except the first and last elements by performing specific operations. It includes a detailed explanation of the problem, examples, and a step-by-step approach to solving it. The document also provides code implementations in C++, Java, Python, and C#.
  
  The document contains a question and an answer to the problem.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # Minimize shifting half of each element to either sides to reduce Array
  
  Last Updated : 28 Mar, 2022
  
  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 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 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 ` `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
  
   ``
  
  Output
  
  `7`
  
  Time Complexity: O(N)
  Auxiliary Space: O(1)
  
  Article Tags :
  Practice Tags :
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document describes a problem involving an array and the task of reducing all elements to 0 except the first and last elements by performing specific operations. It includes a detailed explanation of the problem, examples, and a step-by-step approach to solving it. The document also provides code implementations in C++, Java, Python, and C#.
  
  The document contains a question and an answer to the problem.
  
  Label: question-and-answer