# 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 :
The text passage describes a problem involving an array and the steps required to reduce all elements to 0 except the first and last. It includes a detailed explanation of the problem, an approach to solve it, and code implementations in multiple programming languages. The passage also provides examples and explanations of the steps involved in the solution.
single_question_with_answer

the passage contains a single mathematical question (how to find the minimum number of steps to reduce all array elements to 0 except the first and last) and provides answers to specific examples (e.g., for the input `{2, 3, 3, 4, 7}`, the output is `6`, and for the input `{3, 2, 1, 3, 5, 4}`, the output is `7`).
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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 :
user
The text passage describes a problem involving an array and the steps required to reduce all elements to 0 except the first and last. It includes a detailed explanation of the problem, an approach to solve it, and code implementations in multiple programming languages. The passage also provides examples and explanations of the steps involved in the solution.

TYPE: SINGLE_QUESTION_WITH_ANSWER

The passage contains a single mathematical question (how to find the minimum number of steps to reduce all array elements to 0 except the first and last) and provides answers to specific examples (e.g., for the input `{2, 3, 3, 4, 7}`, the output is `6`, and for the input `{3, 2, 1, 3, 5, 4}`, the output is `7`).