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

By
Sohaib
-
0
8
Adv1


Adv2

Given an array arr[] of dimension N containing solely +1 and -1, the duty is to make the sum of the array zero with the given operation. In a single operation, any ingredient will be up to date as arr[i] = arr[i] * (-1). Every operation price 10 items. the duty is to print the minimal price required to make the sum of the array zero. If the sum can’t be made zero, then print -1.

Examples:

Enter: N = 6, arr[] = {1, 1, -1, -1, 1, 1}
Output: 10
Rationalization: The sum of the array is 2, if we carry out the given operation one time at any index with worth +1, i.e., index: 0, 1, 4, 5 
(0-based indexing), the sum of array turns into 0.

Enter: N = 5, arr[] = {1, 1, -1, -1, 1}
Output: -1
Rationalization: The sum of the array can’t be made zero by making use of any variety of operations.

Strategy: To unravel the issue comply with the beneath thought:

As to make the sum of array 0, there have to be equal variety of +1’s and -1’s. So, we first must test if the N is odd and even, if the N is odd then variety of +1’s and -1’s can by no means be equal so we are able to print -1 straight. Now create two variables positiveOnes and negativeOnes to retailer the variety of +1’s and -1’s respectively. Iterate over the array as soon as and retailer the rely for +1’s and -1’s. Now to get the minimal operations, calculate absolutely the distinction between positiveOnes and negativeOnes and divide it by two. Multiply it by 10 to get the entire price.

Beneath are the steps for the above method:

  • Verify whether or not the scale of the array is odd. Whether it is odd, it returns -1.
  • Initialize two variables positiveOnes and negativeOnes to retailer the entire variety of +1’s and -1’s within the array.
  • Iterate the array and test if arr[i] == 1, increment the counter variable positiveOnes else increment the counter variable negativeOnes.
  • Calculate absolutely the distinction between positiveOnes and negativeOnes and divides it by 2 to get the variety of operations required to make the sum of the array zero.
  • Multiply the variety of operations by 10 to get the entire price.
  • Return the entire price.

Beneath is the implementation for the above method:

C++

#embody <bits/stdc++.h>

utilizing namespace std;

  

int minCost(int arr[], int n)

{

  

    if (n % 2 == 1) {

        return -1;

    }

  

    

    

    int positiveOnes = 0;

  

    

    

    int negativeOnes = 0;

  

    for (int i = 0; i < n; i++) {

        if (arr[i] == 1) {

            positiveOnes++;

        }

        else {

            negativeOnes++;

        }

    }

  

    

    

    

    int totalOperations;

  

    

    

    totalOperations = abs(positiveOnes - negativeOnes) / 2;

    

    int ans = totalOperations * 10;

  

    return ans;

}

  

int important()

{

  

    int n = 6;

    int arr[] = { 1, 1, -1, -1, 1, 1 };

  

    

    cout << "Minimal Value: " << minCost(arr, n);

    return 0;

}

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

Adv3