https://www.geeksforgeeks.org/minimum-incrementdecrement-to-make-array-non-increasing/
https://www.geeksforgeeks.org/minimum-number-increment-operations-make-array-elements-equal/
Given an array a, your task is to convert it into a non-increasing form such that we can either increment or decrement the array value by 1 in minimum changes possible.
Examples :
Input : a[] = {3, 1, 2, 1}
Output : 1
Explanation :
We can convert the array into 3 1 1 1 by
changing 3rd element of array i.e. 2
into its previous integer 1 in one step
hence only one step is required.
Input : a[] = {3, 1, 5, 1}
Output : 4
We need to decrease 5 to 1 to make array sorted
in non-increasing order.
Input : a[] = {1, 5, 5, 5}
Output : 4
We need to increase 1 to 5.
Efficient Approach : Calculate the sum of absolute differences between the final array elements and the current array elements. Thus, the answer will be the sum of the difference between the ith element and the smallest element occurred till then. For this, we can maintain a min-heap to find the smallest element encountered till now. In the min-priority queue, we will put the elements and new elements are compared with the previous minimum. If new minimum is found we will update it, this is done because each of the next element which is coming should be smaller than the current minimum element found till. Here, we calculate the difference so that we can get how much we have to change the current number so that it will be equal or less than previous numbers encountered till. Lastly, the sum of all these difference will be our answer as this will give the final value upto which we have to change the elements.
int DecreasingArray(int a[], int n){ int sum = 0, dif = 0; // min heap priority_queue<int, vector<int>, greater<int> > pq; // Here in the loop we will // check that whether the upcoming // element of array is less than top // of priority queue. If yes then we // calculate the difference. After // that we will remove that element // and push the current element in // queue. And the sum is incremented // by the value of difference for (int i = 0; i < n; i++) { if (!pq.empty() && pq.top() < a[i]) { dif = a[i] - pq.top(); sum += dif; pq.pop(); pq.push(a[i]); } pq.push(a[i]); } return sum;}
We are given an array consisting of n elements. At each operation you can select any one element and increase rest of n-1 elements by 1. You have to make all elements equal performing such operation as many times you wish. Find the minimum number of operations needed for this.
Examples:
Input : arr[] = {1, 2, 3}
Output : Minimum Operation = 3
Explanation :
operation | increased elements | after increment
1 | 1, 2 | 2, 3, 3
2 | 1, 2 | 3, 4, 3
3 | 1, 3 | 4, 4, 4
Input : arr[] = {4, 3, 4}
Output : Minimum Operation = 2
Explanation :
operation | increased elements | after increment
1 | 1, 2 | 5, 4, 4
2 | 2, 3 | 5, 5, 5
Brute force : A simple way to make all elements equal is that at each step find the largest elements and then increase all rest n-1 elements by 1. We should keep doing this operation till all elements become equal. Time Complexity : O(n^2)
Better Approach : If we took a closer look at each operation as well problem statement we will find that increasing all n-1 element except the largest one is similar to decreasing the largest element only. So, the smallest elements need not to decrease any more and rest of elements will got decremented upto smallest one. In this way the total number of operation required for making all elements equal will be arraySum – n * (smallesteElement). Time complexity will be same as that of finding smallest elements and array sum i.e. O(n).
// find array sum sum = arraySum (int arr[], int n); // find the smallest element from array small = smallest (int arr, int n); // calculate min operation required minOperation = sum - (n * small); // return result return minOperation;
// function for finding array sumint arraySum (int arr[], int n){ int sum = 0; for (int i=0; i<n; sum+=arr[i++]); return sum;}// function for finding smallest elementint smallest (int arr[], int n){ int small = INT_MAX; for (int i=0; i<n; i++) if (arr[i] < small) small = arr[i]; return small;}// function for finding min operationint minOp (int arr[], int n){ // find array sum int sum = arraySum (arr, n); // find the smallest element from array int small = smallest (arr, n); // calculate min operation required int minOperation = sum - (n * small); // return result return minOperation;}