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 equallong 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 Codeint 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 approachimport java.io.*;import java.util.*;class GFG{// Function to find minimum cost required// to make all array elements equalstatic 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 Codepublic 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 equaldef 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 Codeif __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 approachusing 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> |
Output:
32
Time Complexity: O(N*logN), for sorting the array
Auxiliary Space: O(N)
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!