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

Given an array arr[] of measurement N containing simplest +1 and -1, the duty is to make the sum of the array 0 with the given operation. In one operation, any part may also be up to date as arr[i] = arr[i] * (-1). Every operation price 10 devices. the duty is to print the minimal price required to make the sum of the array 0. If the sum can’t be made 0, then print -1.

Examples:

Enter: N = 6, arr[] = {1, 1, -1, -1, 1, 1}
Output: 10
Clarification: The sum of the array is two, if we carry out the given operation one time at any index with price +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
Clarification: The sum of the array can’t be made 0 by way of making use of any collection of operations.

Way: To unravel the issue practice the underneath concept:

As to make the sum of array 0, there should be equivalent collection of +1’s and -1’s. So, we first wish to take a look at if the N is extraordinary and even, if the N is extraordinary then collection of +1’s and -1’s can by no means be equivalent so we will print -1 without delay. Now create two variables positiveOnes and negativeOnes to retailer the collection of +1’s and -1’s respectively. Iterate over the array as soon as and retailer the depend for +1’s and -1’s. Now to get the minimal operations, calculate absolutely the distinction between positiveOnes and negativeOnes and divide it by way of two. Multiply it by way of 10 to get the entire price.

Beneath are the stairs for the above method:

  • Take a look at whether or not the dimensions of the array is extraordinary. Whether it is extraordinary, it returns -1.
  • Initialize two variables positiveOnes and negativeOnes to retailer the entire collection of +1’s and -1’s within the array.
  • Iterate the array and take a look at 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 way of 2 to get the collection of operations required to make the sum of the array 0.
  • Multiply the collection of operations by way of 10 to get the entire price.
  • Go back the entire price.

Beneath is the implementation for the above method:

C++

#come with <bits/stdc++.h>

the usage of namespace std;

  

int minCost(int arr[], int n)

{

  

    if (n % 2 == 1) {

        go back -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;

  

    go back ans;

}

  

int primary()

{

  

    int n = 6;

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

  

    

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

    go back 0;

}

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

Like this post? Please share to your friends:
Leave a Reply

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: