Minimum increment/decrement operations required to make Median as X

0 0 5 minutes read

Given an array A[] of n odd integers and an integer X. Calculate the minimum number of operations required to make the median of the array equal to X, where, in one operation we can either increase or decrease any single element by one.

Examples:

Input: A[] = {6, 5, 8}, X = 8
Output: 2
Explanation:
Here 6 can be increased twice. The array will become 8, 5, 8, which becomes 5, 8, 8 after sorting, hence the median is equal to 8.

Input: A[] = {1, 4, 7, 12, 3, 5, 9}, X = 5
Output: 0
Explanation:
After sorting 5 is in middle position hence 0 steps are required.

Approach: The idea for changing the median of the array will be to sort the given array. Then after sorting, the best possible candidate for making the median is the middle element because it will be better to reduce the numbers before the middle element as they are smaller and increase the numbers after the middle element as they are larger.

Below is the implementation of the above approach:

C++

// C++ implementation to determine the 
// Minimum numbers of steps to make 
// median of an array equal X 
 
#include <bits/stdc++.h> 
using namespace std; 
 
// Function to count minimum 
// required operations to 
// make median X 
int count(vector<int> a, int X) 
{ 
    // Sorting the array a[] 
    sort(a.begin(), a.end()); 
    int ans = 0; 
 
    // Calculate the size of array 
    int n = a.size(); 
 
    // Iterate over the array 
    for (int i = 0; i < n; i++) { 
        // For all elements 
        // less than median 
        if (i < n / 2) 
            ans += max(0, a[i] - X); 
 
        // For element equal 
        // to median 
        else if (i == n / 2) 
            ans += abs(X - a[i]); 
 
        // For all elements 
        // greater than median 
        else
            ans += max(0, X - a[i]); 
    } 
 
    // Return the answer 
    return ans; 
} 
 
// Driver code 
int main() 
{ 
    vector<int> a = { 6, 5, 8 }; 
    int X = 8; 
    cout << count(a, X) << "\n"; 
    return 0; 
} 

Java

// Java implementation to determine the
// Minimum numbers of steps to make
// median of an array equal X
import java.util.*;
 
class GFG{
 
// Function to count minimum
// required operations to
// make median X
static int count(int[] a, int X)
{
     
    // Sorting the array a[]
    Arrays.sort(a);
    int ans = 0;
 
    // Calculate the size of array
    int n = a.length;
 
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        
       // For all elements
       // less than median
       if (i < n / 2)
           ans += Math.max(0, a[i] - X);
        
       // For element equal
       // to median
       else if (i == n / 2)
           ans += Math.abs(X - a[i]);
       
       // For all elements
       // greater than median
       else
           ans += Math.max(0, X - a[i]);
    }
     
    // Return the answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int []a = { 6, 5, 8 };
    int X = 8;
     
    System.out.print(count(a, X) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 implementation to determine the 
# Minimum numbers of steps to make 
# median of an array equal X 
 
# Function to count minimum 
# required operations to 
# make median X 
def count(a, X): 
 
    # Sorting the array a[] 
    a.sort()
    ans = 0
 
    # Calculate the size of array 
    n = len(a)
 
    # Iterate over the array 
    for i in range(n):
         
        # For all elements 
        # less than median 
        if (i < n // 2): 
            ans += max(0, a[i] - X)
 
        # For element equal 
        # to median 
        elif (i == n // 2): 
            ans += abs(X - a[i]) 
 
        # For all elements 
        # greater than median 
        else:
            ans += max(0, X - a[i]); 
 
    # Return the answer 
    return ans
 
# Driver code
a = [ 6, 5, 8 ] 
X = 8
 
print(count(a, X)) 
 
# This code is contributed by divyeshrabadiya07

C#

// C# implementation to determine the
// Minimum numbers of steps to make
// median of an array equal X
using System;
 
class GFG{
 
// Function to count minimum
// required operations to
// make median X
static int count(int[] a, int X)
{
     
    // Sorting the array []a
    Array.Sort(a);
    int ans = 0;
 
    // Calculate the size of array
    int n = a.Length;
 
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        
       // For all elements
       // less than median
       if (i < n / 2)
           ans += Math.Max(0, a[i] - X);
            
       // For element equal
       // to median
       else if (i == n / 2)
           ans += Math.Abs(X - a[i]);
        
       // For all elements
       // greater than median
       else
           ans += Math.Max(0, X - a[i]);
    }
     
    // Return the answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 6, 5, 8 };
    int X = 8;
     
    Console.Write(count(a, X) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript implementation to determine the
// Minimum numbers of steps to make
// median of an array equal X
 
// 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 the sorted array
    return (arr);
}
 
// Function to count minimum
// required operations to
// make median X
function count(a, X)
{
     
    // Sorting the array a
    a  = bblSort(a);
    var ans = 0;
 
    // Calculate the size of array
    var n = a.length;
 
    // Iterate over the array
    for(i = 0; i < n; i++) 
    {
         
        // For all elements
        // less than median
        if (i < parseInt(n / 2))
            ans += Math.max(0, a[i] - X);
 
        // For element equal
        // to median
        else if (i == parseInt(n / 2))
            ans += Math.abs(X - a[i]);
 
        // For all elements
        // greater than median
        else
            ans += Math.max(0, X - a[i]);
    }
     
    // Return the answer
    return ans;
}
 
// Driver code
var a = [ 6, 5, 8 ];
var X = 8;
 
document.write(count(a, X));
 
// This code is contributed by aashish1995
 
</script>

Output:

Time Complexity: O(N * log N)
Auxiliary Space Complexity: O(1)

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 zambiatek!