Min cost required to make the Array sum zero consisting of 1 and -1

Given an array arr[] of size N containing only +1 and -1, the task is to make the sum of the array zero with the given operation. In a single operation, any element can be updated as arr[i] = arr[i] * (-1). Each operation cost 10 units. the task is to print the minimum cost required to make the sum of the array zero. If the sum cannot be made zero, then print -1.

Examples:

Input: N = 6, arr[] = {1, 1, -1, -1, 1, 1}
Output: 10
Explanation: The sum of the array is 2, if we perform the given operation one time at any index with value +1, i.e., index: 0, 1, 4, 5 
(0-based indexing), the sum of array becomes 0.

Input: N = 5, arr[] = {1, 1, -1, -1, 1}
Output: -1
Explanation: The sum of the array cannot be made zero by applying any number of operations.

Approach: To solve the problem follow the below idea:

As to make the sum of array 0, there must be equal number of +1’s and -1’s. So, we first need to check if the N is odd or even, if the N is odd then number of +1’s and -1’s can never be equal so we can print -1 directly. Now create two variables positiveOnes and negativeOnes to store the number of +1’s and -1’s respectively. Iterate over the array once and store the count for +1’s and -1’s. Now to get the minimum operations, calculate the absolute difference between positiveOnes and negativeOnes and divide it by two. Multiply it by 10 to get the total cost.

Below are the steps for the above approach:

• Check whether the size of the array is odd. If it is odd, it returns -1.
• Initialize two variables positiveOnes and negativeOnes to store the total number of +1’s and -1’s in the array.
• Iterate the array and check if arr[i] == 1, increment the counter variable positiveOnes else increment the counter variable negativeOnes.
• Calculate the absolute difference between positiveOnes and negativeOnes and divides it by 2 to get the number of operations required to make the sum of the array zero.
• Multiply the number of operations by 10 to get the total cost.
• Return the total cost.

Below is the implementation for the above approach:

Time Complexity: O(n)
Auxiliary Space: O(n)

Given an array arr[] of size N containing only +1 and -1, the task is to make the sum of the array zero with the given operation. In a single operation, any element can be updated as arr[i] = arr[i] * (-1). Each operation cost 10 units. the task is to print the minimum cost required to make the sum of the array zero. If the sum cannot be made zero, then print -1.

Examples:

Input: N = 6, arr[] = {1, 1, -1, -1, 1, 1}
Output: 10
Explanation: The sum of the array is 2, if we perform the given operation one time at any index with value +1, i.e., index: 0, 1, 4, 5 
(0-based indexing), the sum of array becomes 0.

Input: N = 5, arr[] = {1, 1, -1, -1, 1}
Output: -1
Explanation: The sum of the array cannot be made zero by applying any number of operations.

Approach: To solve the problem follow the below idea:

As to make the sum of array 0, there must be equal number of +1’s and -1’s. So, we first need to check if the N is odd or even, if the N is odd then number of +1’s and -1’s can never be equal so we can print -1 directly. Now create two variables positiveOnes and negativeOnes to store the number of +1’s and -1’s respectively. Iterate over the array once and store the count for +1’s and -1’s. Now to get the minimum operations, calculate the absolute difference between positiveOnes and negativeOnes and divide it by two. Multiply it by 10 to get the total cost.

Below are the steps for the above approach:

• Check whether the size of the array is odd. If it is odd, it returns -1.
• Initialize two variables positiveOnes and negativeOnes to store the total number of +1’s and -1’s in the array.
• Iterate the array and check if arr[i] == 1, increment the counter variable positiveOnes else increment the counter variable negativeOnes.
• Calculate the absolute difference between positiveOnes and negativeOnes and divides it by 2 to get the number of operations required to make the sum of the array zero.
• Multiply the number of operations by 10 to get the total cost.
• Return the total cost.

Below is the implementation for the above approach:

Time Complexity: O(n)
Auxiliary Space: O(n)