Given an array arr[] of positive integers and three integers A, R, M, where
- The cost of adding 1 to an element of the array is A,
- the cost of subtracting 1 from an element of the array is R and
- the cost of adding 1 to an element and subtracting 1 from another element simultaneously is M.
The task is to find the minimum total cost to make all the elements of the array equal.
Examples:
Input: arr[] = {5, 5, 3, 6, 5}, A = 1, R = 2, M = 4
Output: 4
Explanation:
Operation 1: Add two times to element 3, Array – {5, 5, 5, 6, 5}, Cost = 2
Operation 2: Subtract one time to element 6, Array – {5, 5, 5, 5, 5}, Cost = 4
Therefore, minimum cost is 4.Input: arr[] = {5, 5, 3, 6, 5}, A = 1, R = 2, M = 2
Output: 3
Approach: The idea is to:
- find the minimum of the M and A + R as M can make both operations simultaneously.
- Then, store prefix sum in an array to find the sum in constant time.
- Now for each element calculate the cost of making equal to the current element and find the minimum of them.
- The smallest answer can also exist when we make all elements equal to the average of the array.
- Therefore, at the end also compute the cost for making all elements equal to the approximate average sum of elements.
Below is the implementation of above approach:
C++
// C++ implementation to find the// minimum cost to make all array// elements equal#include <bits/stdc++.h>using namespace std;// Function that returns the cost of// making all elements equal to current elementint costCalculation( int current, int arr[], int n, int pref[], int a, int r, int minimum){ // Compute the lower bound // of current element int index = lower_bound( arr, arr + n, current) - arr; // Calculate the requirement // of add operation int left = index * current - pref[index]; // Calculate the requirement // of subtract operation int right = pref[n] - pref[index] - (n - index) * current; // Compute minimum of left and right int res = min(left, right); left -= res; right -= res; // Computing the total cost of add // and subtract operations int total = res * minimum; total += left * a; total += right * r; return total;}// Function that prints minimum cost// of making all elements equalvoid solve(int arr[], int n, int a, int r, int m){ // Sort the given array sort(arr, arr + n); // Calculate minimum from a + r and m int minimum = min(a + r, m); int pref[n + 1] = { 0 }; // Compute prefix sum // and store in pref // array for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i]; int ans = 10000; // Find the minimum cost // from the given elements for (int i = 0; i < n; i++) ans = min( ans, costCalculation( arr[i], arr, n, pref, a, r, minimum)); // Finding the minimum cost // from the other cases where // minimum cost can occur ans = min( ans, costCalculation( pref[n] / n, arr, n, pref, a, r, minimum)); ans = min( ans, costCalculation( pref[n] / n + 1, arr, n, pref, a, r, minimum)); // Printing the minimum cost of making // all elements equal cout << ans << "\n";}// Driver Codeint main(){ int arr[] = { 5, 5, 3, 6, 5 }; int A = 1, R = 2, M = 4; int size = sizeof(arr) / sizeof(arr[0]); // Function Call solve(arr, size, A, R, M); return 0;} |
Java
// Java implementation to find the// minimum cost to make all array// elements equalimport java.lang.*;import java.util.*;class GFG{public static int lowerBound(int[] array, int length, int value){ int low = 0; int high = length; while (low < high) { final int mid = (low + high) / 2; // Checks if the value is less // than middle element of the array if (value <= array[mid]) { high = mid; } else { low = mid + 1; } } return low;}// Function that returns the cost of making // all elements equal to current elementpublic static int costCalculation(int current, int arr[], int n, int pref[], int a, int r, int minimum){ // Compute the lower bound // of current element int index = lowerBound(arr, arr.length, current); // Calculate the requirement // of add operation int left = index * current - pref[index]; // Calculate the requirement // of subtract operation int right = pref[n] - pref[index]- (n - index)* current; // Compute minimum of left and right int res = Math.min(left, right); left -= res; right -= res; // Computing the total cost of add // and subtract operations int total = res * minimum; total += left * a; total += right * r; return total;}// Function that prints minimum cost// of making all elements equalpublic static void solve(int arr[], int n, int a, int r, int m){ // Sort the given array Arrays.sort(arr); // Calculate minimum from a + r and m int minimum = Math.min(a + r, m); int []pref = new int [n + 1]; Arrays.fill(pref, 0); // Compute prefix sum and // store in pref array for(int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i]; int ans = 10000; // Find the minimum cost // from the given elements for(int i = 0; i < n; i++) ans = Math.min(ans, costCalculation(arr[i], arr, n, pref, a, r, minimum)); // Finding the minimum cost // from the other cases where // minimum cost can occur ans = Math.min(ans, costCalculation(pref[n] / n, arr, n, pref, a, r, minimum)); ans = Math.min(ans, costCalculation(pref[n] / n + 1, arr, n, pref, a, r, minimum)); // Printing the minimum cost of making // all elements equal System.out.println(ans);}// Driver Codepublic static void main(String args[]){ int arr[] = { 5, 5, 3, 6, 5 }; int A = 1, R = 2, M = 4; int size = arr.length ; // Function Call solve(arr, size, A, R, M);}}// This code is contributed by SoumikMondal |
Python3
# Python3 implementation to find the# minimum cost to make all array# elements equaldef lowerBound(array, length, value): low = 0 high = length while (low < high): mid = (low + high) // 2 # Checks if the value is less # than middle element of the array if (value <= array[mid]): high = mid else: low = mid + 1 return low# Function that returns the cost of making # all elements equal to current elementdef costCalculation(current, arr, n, pref, a, r, minimum): # Compute the lower bound # of current element index = lowerBound(arr, len(arr), current) # Calculate the requirement # of add operation left = index * current - pref[index] # Calculate the requirement # of subtract operation right = (pref[n] - pref[index] - (n - index) * current) # Compute minimum of left and right res = min(left, right) left -= res right -= res # Computing the total cost of add # and subtract operations total = res * minimum total += left * a total += right * r return total# Function that prints minimum cost# of making all elements equaldef solve(arr, n, a, r, m): # Sort the given array arr.sort() # Calculate minimum from a + r and m minimum = min(a + r, m) pref = [0] * (n + 1) # Compute prefix sum and # store in pref array for i in range(n): pref[i + 1] = pref[i] + arr[i] ans = 10000 # Find the minimum cost # from the given elements for i in range(n): ans = min(ans, costCalculation(arr[i], arr, n, pref, a, r, minimum)) # Finding the minimum cost # from the other cases where # minimum cost can occur ans = min(ans, costCalculation(pref[n] // n, arr, n, pref, a, r, minimum)) ans = min(ans, costCalculation(pref[n] // n + 1, arr, n, pref, a, r, minimum)) # Printing the minimum cost of making # all elements equal print(ans)# Driver Codeif __name__ == "__main__": arr = [ 5, 5, 3, 6, 5 ] A = 1 R = 2 M = 4 size = len(arr) # Function call solve(arr, size, A, R, M)# This code is contributed by chitranayal |
C#
// C# implementation to find the// minimum cost to make all array// elements equalusing System;class GFG{public static int lowerBound(int[] array, int length, int value){ int low = 0; int high = length; while (low < high) { int mid = (low + high) / 2; // Checks if the value is less // than middle element of the array if (value <= array[mid]) { high = mid; } else { low = mid + 1; } } return low;}// Function that returns the cost of making // all elements equal to current elementpublic static int costCalculation(int current, int []arr, int n, int []pref, int a, int r, int minimum){ // Compute the lower bound // of current element int index = lowerBound(arr, arr.Length, current); // Calculate the requirement // of add operation int left = index * current - pref[index]; // Calculate the requirement // of subtract operation int right = pref[n] - pref[index] - (n - index) * current; // Compute minimum of left and right int res = Math.Min(left, right); left -= res; right -= res; // Computing the total cost of add // and subtract operations int total = res * minimum; total += left * a; total += right * r; return total;}// Function that prints minimum cost// of making all elements equalpublic static void solve(int []arr, int n, int a, int r, int m){ // Sort the given array Array.Sort(arr); // Calculate minimum from a + r and m int minimum = Math.Min(a + r, m); int []pref = new int [n + 1]; Array.Fill(pref, 0); // Compute prefix sum and // store in pref array for(int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i]; int ans = 10000; // Find the minimum cost // from the given elements for(int i = 0; i < n; i++) ans = Math.Min(ans, costCalculation(arr[i], arr, n, pref, a, r, minimum)); // Finding the minimum cost // from the other cases where // minimum cost can occur ans = Math.Min(ans, costCalculation(pref[n] / n, arr, n, pref, a, r, minimum)); ans = Math.Min(ans, costCalculation(pref[n] / n + 1, arr, n, pref, a, r, minimum)); // Printing the minimum cost of making // all elements equal Console.WriteLine(ans);}// Driver Codepublic static void Main(string []args){ int []arr = { 5, 5, 3, 6, 5 }; int A = 1, R = 2, M = 4; int size = arr.Length ; // Function Call solve(arr, size, A, R, M);}}// This code is contributed by SoumikMondal |
Javascript
<script>// javascript implementation to find the// minimum cost to make all array// elements equal function lowerBound(array, length, value) { var low = 0; var high = length; while (low < high) { var mid = parseInt((low + high) / 2); // Checks if the value is less // than middle element of the array if (value <= array[mid]) { high = mid; } else { low = mid + 1; } } return low; } // Function that returns the cost of making // all elements equal to current element function costCalculation(current , arr , n , pref , a , r , minimum) { // Compute the lower bound // of current element var index = lowerBound(arr, arr.length, current); // Calculate the requirement // of add operation var left = index * current - pref[index]; // Calculate the requirement // of subtract operation var right = pref[n] - pref[index] - (n - index) * current; // Compute minimum of left and right var res = Math.min(left, right); left -= res; right -= res; // Computing the total cost of add // and subtract operations var total = res * minimum; total += left * a; total += right * r; return total; } // Function that prints minimum cost // of making all elements equal function solve(arr , n , a , r , m) { // Sort the given array arr.sort(); // Calculate minimum from a + r and m var minimum = Math.min(a + r, m); var pref = Array(n+1).fill(0); // Compute prefix sum and // store in pref array for (i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i]; var ans = 10000; // Find the minimum cost // from the given elements for (i = 0; i < n; i++) ans = Math.min(ans, costCalculation(arr[i], arr, n, pref, a, r, minimum)); // Finding the minimum cost // from the other cases where // minimum cost can occur ans = Math.min(ans, costCalculation(pref[n] / n, arr, n, pref, a, r, minimum)); ans = Math.min(ans, costCalculation(pref[n] / n + 1, arr, n, pref, a, r, minimum)); // Printing the minimum cost of making // all elements equal document.write(ans); } // Driver Code var arr = [ 5, 5, 3, 6, 5 ]; var A = 1, R = 2, M = 4; var size = arr.length; // Function Call solve(arr, size, A, R, M);// This code is contributed by Rajput-Ji.</script> |
Output:
4
Time Complexity: O(n log n), used for sorting
Auxiliary Space: O(n), as extra space is used of size n to create prefix array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
