Minimum Increment and Decrement operations to make array elements equal

Reading time: 30 minutes | Coding time: 10 minutes

We are given an array, we need to find the minimum number of increment and decrement operations (by 1) required to make all the array elements equal.

Let us understand this problem with the help of an example:

We need to make the elements of this array equal : arr [] = {2,4,5,7,10}.

It is important to note here, that though we can make the array elements equal to any number in the array but we are asked to find out the minimum number of operations.So,we should find a number which minimizes the cost of equalizing the elements and that number is the middle element.Hence,we will be incrementing and decrementing the array elements to make them equal to the middle element i.e 5.

(This is explained in detail under the heading : Method 2)
x[0] => 5 - 2 = 3 (3 increments)
x[1] => 5 - 4 = 1 (1 increment)
x[2] => 5 - 5 = 0
x[3] => 7 - 5 = 2 (2 decrements)
x[4] => 10 - 5 = 5 (5 decrements)
Minimum number of operations = 3 + 1 + 2 + 5 = 11 with 4 increments and 7 decrements.These operations will result in :arr[] = {5,5,5,5,5}

We have explored two methods:

• Method 1: Brute force approach O(N^2) time
• Method 2: Efficient approach O(N logN) time

Method 1

Concept

A brute force approach can be to check the number of operations required to equalize all the elements to each element in the array,one by one and then return the minimum of these values.This will be quite time consuming (O(N^2) run time) and inefficient.

Algorithm

Step 1:Run a loop from index i = 0 to index i = n-1.
Step 2:For every element, run another loop, from j = 0 to j = n-1.
Step 3:Maintain a current result which stores the sum of absolute difference between arr[i] and arr[j].
Step 4: After the each traversal of the inner loop, result is assigned the minimum of current result and it's previous value.
Step 5:After termination of the outer loop, return result.

Implementation

#include<iostream>
using namespace std;
int min_Ops(int arr[],int n)
{
    int res  = MAX_INT;
    int curr_res = 0;
    for(int i=0;i<n;i++)
    {
        curr_res = 0;
        for(int j=0;j<n;j++)
        {
            curr_res = curr_res + abs(arr[i] - arr[j]);
        }
        res = min(res,curr_res);
    }
    return res;
}
int main()
{
    int arr[] = {3,7,9,10};;
    cout<<min_Ops()<<endl;
}

Output

9

Example

Let us consider an array = {3,7,9,10}
and res = MAX_INT, curr_res = 0

arr[ ] =	3	7	9	10
curr_res	17	9	9	11
res	17	9	9	9

i = 0: arr[0] = 3
curr_res = |3 - 3| + |3 - 7| + |3 - 9| + |3 - 10| = 0 + 4 + 6 + 7 = 17
res = min(MAX_INT,17) = 17
i = 1:arr[1] = 7
curr_res = |7 - 3| + |7 - 7| + |7 - 9| + |7 - 10| = 4 + 0 + 2 + 3 = 9
res = min(17,9) = 9
i = 2:arr[2] = 9
curr_res = |9 - 3| + |9 - 7| + |9 - 9| + |9 - 10| = 6 + 2 + 0 + 1 = 9
res = min(9,9) = 9
i = 3:arr[3] = 10
curr_res = |10 - 3| + |10 - 7| + |10 - 9| + |10 - 10| = 7 + 3 + 1 + 0 = 11
res = min(9,11) = 9

res = 9

Time Complexity = O(n^2)

We run 2 for loops, one for picking an element in the array and the other for equalizing all the elements of the array to the chosen element.

Space complexity = O(1)

It uses constant space for alll input sizes.

Method 2:

Concept

For calculating minimum number of operations to equalize an array, we need to make sure that all the elements are incremented to a value, so that they become equal in the least number of increment/decrement operations.For this, we should select a number which is, basically, nearest to all the elements in the array.

This element will be the middle element of a sorted array.All the elements to the left of this element, will be incremented to its value and all the elements to its right will be decremented to its value.

Algorithm

Step 1:Sort the array.
Step 2:Find the median of the array.If the array is of odd length, only one median is obtained.If the array is of even length, we obtain 2 medians.
Step 3:Now, start traversing the array, and add the absolute difference of the median and arr[i] to the sum.For even length arrays, repeat this step for both the medians.
Step 4:After reaching the end of the array,we return the minimum sum.

Implementation

Java Implementation :

import java.util.*;
static int minOps(int arr[],int n)
{
    Arrays.sort(arr);
    int mid = arr[n/2];
    int mid1 = arr[(n/2) - 1];
    int res = 0,res1 = 0;
    for(int i=0;i<n;i++)
    {
        res = res +  Math.abs(arr[i] - mid);
        res1 = res1 + Math.abs(arr[i] - mid1);
    }
    return Math.min(res,res1);
}

public static void main(String args[])
{
    int arr1[] = {2,5,7,9,10};
    int arr2[] = {3,7,9,10};
    System.out.println(minOps(arr1,arr1.length));
    System.out.println(minOps(arr2,arr2.length));
}

Output

12
9

C++ implementation :

#include<iostream>
using namespace std;
int min_ops(int arr[],int n)
{
    int mid = arr[n/2];
	int mid1 = arr[(n/2)-1];
	int res = 0,res1 = 0;
	for(int i=0;i<n;i++)
	{
		res = res + abs(arr[i] - mid);
		res1 = res1 +abs(arr[i] - mid1);
	}
	return min(res,res1);
}
int main()
{
    int arr1[] = {2,5,7,9,10};
    int arr2[] = {3,7,9,10};
    cout<<min_ops(arr1,5)<<endl;
    cout<<min_ops(arr2,4)<<endl;   
}

Output

12
9

Example

1) arr1[ ] = {2,5,7,9,10};
median = 7, res = 0

arr[ ] =	2	5	7	9	10
abs(median - arr[i])	5	2	0	2	3
res = 5 + 2 + 0 + 2 + 3 = 12

2) arr2[] = {3,7,9,10};
median1 = 7, median2 = 9
res = 0,res1 = 0;

arr[ ] =	3	7	9	10
abs(median1 - arr[i])	4	0	2	3
res = 4 + 0 + 2 + 3 = 9

arr[ ] =	3	7	9	10
abs(median2 - arr[i])	6	2	0	1
res1 = 6 + 2 + 0 + 1 = 9

min( res , res1 ) = 9

Time Complexity : O(n * logn)

This algorithm runs in O(n * logn) time for an unsorted array.It takes O(n * logn) time to sort the array and O(n) time to traverse it once.
As, O(n * logn) + O(n) = O(n * logn)
If the input array is always sorted, the time complexity of this algorithm is O(n).

Space complexity : O(1)

It takes constant space for any inout size.

With this article at OpenGenus, you must have the complete idea of the algorithm to find the minimum Increment and Decrement operations to make array elements equal. Enjoy.