Minimize cost required to make all array elements greater than or equal to zero

Minimize cost required to make all array elements greater than or equal to zero

Given an array arr[] consisting of N integers and an integer X, the task is to find the minimum cost required to make all array elements greater than or equal to 0 by performing the following operations any number of times:

• Increase any array element by 1. Cost = 1.
• Increase all array elements by 1. Cost = X.

Examples:

Input: arr[] = {-1, -3, 3, 4, 5}, X = 2
Output: 4
Explanation:
Increment arr[0] by 1. The array arr[] modifies to {0, -3, 3, 4, 5}. Cost = 1.
Increment arr[1] by 1 thrice. The array arr[] modifies to {0, 0, 3, 4, 5}. Therefore, Cost = 4.
Hence, the total cost required is 4.

Input: arr[] = {-3, -2, -1, -5, 7}, X = 2
Output: 8   

Approach: The idea is to use Greedy Approach to solve the problem. Follow the steps below to solve the problem:

• Sort the array arr[] in ascending order.
• Initialize an auxiliary vector, say list, to store the negative array elements.
• Initialize a variable, cost = 0, to store the cost required to make the current array element  0 and another variable, min_cost = INT_MAX, to store the final minimum cost to make all array elements >= 0.
• Traverse the array arr[] and try to convert all the array elements in the list >= 0 by applying the suitable operations and update min_cost accordingly.
• Print the value of min_cost as the answer.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void minCost(int arr[], int N, int X) {               sort(arr, arr + N);        int sum = 0;                  int cost = 0;                  int min_cost = INT_MAX;                  for (int i = 0; i < N; i++) {                              if (arr[i] < 0) {                                          cost = abs(arr[i]) * X                    + (sum - abs(arr[i]) * i);             sum += abs(arr[i]);                             min_cost = min(min_cost, cost);         }     }             cout << min_cost; }    int main() {          int arr[] = { -1, -3, -2, 4, -1 };             int N = sizeof(arr) / sizeof(arr[0]);             int X = 2;                  minCost(arr, N, X);        return 0; }

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)