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 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 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[n1] 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, N1), 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, N1), 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, N1), 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[n1]
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++

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