Given a sorted array arr[] of size N (1 ? N ? 105) and two integers A and B, the task is to calculate the minimum cost required to make all array elements equal by increments or decrements. The cost of each increment and decrement are A and B respectively.
Examples:
Input: arr[] = { 2, 5, 6, 9, 10, 12, 15 }, A = 1, B = 2
Output: 32
Explanation:
Increment arr[0] by 8, arr[1] by 5, arr[2] by 4, arr[3] by 1, arr[4] by 0. Decrement arr[5] by 2, arr[6] by 5.
Therefore, arr[] modifies to { 10, 10, 10, 10, 10, 10, 10 }.
Therefore, total cost required = (8 + 5 + 4 + 1 + 0) * 1 + (2 + 5) * 2 = 18 + 14 = 32Input: arr[] = { 2, 3, 4 }, A = 10, B = 1
Output: 3
Approach: Follow the steps below the implementation:
- Sort the array in ascending order.
- Traverse the array.
- Initialize a new array to store the cumulative prefix sum.
- If A and B both are equal, then the mid element will have the minimum cost.
- If A is less than B, then the minimum cost element is present on the right side of mid by setting low = mid + 1. Search for that element using Binary Search technique.
- If A is greater than B, then the minimum cost element is present on the left side of mid. Search for that element using Binary Search technique by setting high = mid – 1.
Below is the implementation of the above approach.
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum cost // required to make all array elements equal long long minCost( int arr[], int A, int B, int N) { // Sort the array sort(arr, arr + N); // Stores the prefix sum and sum // of the array respectively long long cumarr[N], sum = 0; // Traverse the array for ( int i = 0; i < N; i++) { // Update sum sum += arr[i]; // Update prefix sum cumarr[i] = sum; } // Update middle element int mid = (N - 1) / 2; // Calculate cost to convert // every element to mid element long long ans = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (A == B) return ans; else if (A < B) { int low = mid, high = N - 1; // Binary search while (low <= high) { mid = low + (high - low) / 2; long long curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans) { ans = curr; low = mid + 1; } else high = mid - 1; } return ans; } else { int low = 0, high = mid; // Binary search while (low <= high) { mid = low + (high - low) / 2; long long curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans) { ans = curr; high = mid - 1; } else low = mid + 1; } return ans; } } // Driver Code int main() { int arr[] = { 2, 5, 6, 9, 10, 12, 15 }; int A = 1, B = 2; int N = sizeof (arr) / sizeof (arr[0]); cout << minCost(arr, A, B, N); return 0; } |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to find minimum cost required // to make all array elements equal static int minCost( int [] arr, int A, int B, int N) { // Sort the array Arrays.sort(arr); // Stores the prefix sum and sum // of the array respectively int [] cumarr = new int [N]; int sum = 0 ; // Traverse the array for ( int i = 0 ; i < N; i++) { // Update sum sum += arr[i]; // Update prefix sum cumarr[i] = sum; } // Update middle element int mid = (N - 1 ) / 2 ; // Calculate cost to convert // every element to mid element int ans = (arr[mid] * (mid + 1 ) - cumarr[mid]) * A + (cumarr[N - 1 ] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (A == B) return ans; else if (A < B) { int low = mid, high = N - 1 ; // Binary search while (low <= high) { mid = low + (high - low) / 2 ; int curr = (arr[mid] * (mid + 1 ) - cumarr[mid]) * A + (cumarr[N - 1 ] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans) { ans = curr; low = mid + 1 ; } else high = mid - 1 ; } return ans; } else { int low = 0 , high = mid; // Binary search while (low <= high) { mid = low + (high - low) / 2 ; int curr = (arr[mid] * (mid + 1 ) - cumarr[mid]) * A + (cumarr[N - 1 ] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans) { ans = curr; high = mid - 1 ; } else low = mid + 1 ; } return ans; } } // Driver Code public static void main(String[] args) { int [] arr = { 2 , 5 , 6 , 9 , 10 , 12 , 15 }; int A = 1 , B = 2 ; int N = ( int )(arr.length); System.out.println(minCost(arr, A, B, N)); } } // This code is contributed by susmitakundugoaldanga |
Python3
# Python program to implement # the above approach # Function to find minimum cost required # to make all array elements equal def minCost(arr, A, B, N): # Sort the array arr.sort(); # Stores the prefix sum and sum # of the array respectively cumarr = [ 0 ] * N; sum = 0 ; # Traverse the array for i in range (N): # Update sum sum + = arr[i]; # Update prefix sum cumarr[i] = sum ; # Update middle element mid = (N - 1 ) / / 2 ; # Calculate cost to convert # every element to mid element ans = (arr[mid] * (mid + 1 ) - cumarr[mid]) * A\ + (cumarr[N - 1 ] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (A = = B): return ans; elif (A < B): low = mid; high = N - 1 ; # Binary search while (low < = high): mid = low + (high - low) / / 2 ; curr = (arr[mid] * (mid + 1 ) - cumarr[mid]) * A\ + (cumarr[N - 1 ] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr < = ans): ans = curr; low = mid + 1 ; else : high = mid - 1 ; return ans; else : low = 0 ; high = mid; # Binary search while (low < = high): mid = low + (high - low) / / 2 ; curr = (arr[mid] * (mid + 1 ) - cumarr[mid]) * A\ + (cumarr[N - 1 ] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr < = ans): ans = curr; high = mid - 1 ; else : low = mid + 1 ; return ans; # Driver Code if __name__ = = '__main__' : arr = [ 2 , 5 , 6 , 9 , 10 , 12 , 15 ]; A = 1 ; B = 2 ; N = ( int )( len (arr)); print (minCost(arr, A, B, N)); # This code is contributed by 29AjayKumar |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to find minimum cost // required to make all array elements equal static ulong minCost( ulong [] arr, ulong A, ulong B, ulong N) { // Sort the array Array.Sort(arr); // Stores the prefix sum and sum // of the array respectively ulong [] cumarr = new ulong [N]; ulong sum = 0; // Traverse the array for ( ulong i = 0; i < N; i++) { // Update sum sum += arr[i]; // Update prefix sum cumarr[i] = sum; } // Update middle element ulong mid = (N - 1) / 2; // Calculate cost to convert // every element to mid element ulong ans = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (A == B) return ans; else if (A < B) { ulong low = mid, high = N - 1; // Binary search while (low <= high) { mid = low + (high - low) / 2; ulong curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans) { ans = curr; low = mid + 1; } else high = mid - 1; } return ans; } else { ulong low = 0, high = mid; // Binary search while (low <= high) { mid = low + (high - low) / 2; ulong curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans) { ans = curr; high = mid - 1; } else low = mid + 1; } return ans; } } // Driver Code public static void Main() { ulong [] arr = { 2, 5, 6, 9, 10, 12, 15 }; ulong A = 1, B = 2; ulong N = ( ulong )(arr.Length); Console.Write(minCost(arr, A, B, N)); } } // This code is contributed by subhammahato348 |
Javascript
<script> // Javascript program to implement // the above approach // Creating the bblSort function function bblSort(arr){ for ( var i = 0; i < arr.length; i++){ // Last i elements are already in place for ( var j = 0; j < ( arr.length - i -1 ); j++){ // Checking if the item at present iteration // is greater than the next iteration if (arr[j] > arr[j+1]){ // If the condition is true then swap them var temp = arr[j] arr[j] = arr[j + 1] arr[j+1] = temp } } } return arr; } // Function to find minimum cost required // to make all array elements equal function minCost(arr , A , B , N) { // Sort the array arr = bblSort(arr); // Stores the prefix sum and sum // of the array respectively var cumarr = Array(N).fill(0); var sum = 0; // Traverse the array for (i = 0; i < N; i++) { // Update sum sum += arr[i]; // Update prefix sum cumarr[i] = sum; } // Update middle element var mid = ((N - 1) / 2); // Calculate cost to convert // every element to mid element var ans = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B-2; if (A == B) return ans; else if (A < B) { var low = mid, high = N - 1; // Binary search while (low <= high) { mid = low + (high - low) / 2; var curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 2] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans) { ans = curr; low = mid + 1; } else high = mid - 1; } return ans; } else { var low = 0, high = mid; // Binary search while (low <= high) { mid = low + ((high - low) / 2); var curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans) { ans = curr; high = mid - 1; } else low = mid + 1; } return ans; } } // Driver Code var arr = [ 2, 5, 6, 9, 10, 12, 15 ]; var A = 1, B = 2; var N = parseInt(arr.length); document.write(minCost(arr, A, B, N)); // This code contributed by umadevi9616 </script> |
32
Time Complexity: O(N*logN), for sorting the array
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!