Maximize the median of the given array after adding K elements to the same array

0 0 4 minutes read

Given an array arr[] of N elements and an integer K where K < N. The task is to insert K integer elements to the same array such that the median of the resultant array is maximized. Print the maximized median.
Examples:

Input: arr[] = {3, 2, 3, 4, 2}, k = 2
Output: 3
{2, 2, 3, 3, 4, 5, 5} can be once such resultant array with 3 as the median.
Input: arr[] = {3, 2, 3, 4, 2}, k = 3
Output: 3.5

Approach: In order to maximize the median of the resultant array, all the elements that need to be inserted must be greater than the maximum element from the array. After inserting these elements, the new size of the array will be size = N + K. Sort the array and the median of the array will be arr[size / 2] if the size is odd else (arr[(size / 2) – 1] + arr[size / 2]) / 2.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to return the maximized median 
float getMaxMedian(int arr[], int n, int k) 
{ 
    int size = n + k; 
  
    // Sort the array 
    sort(arr, arr + n); 
  
    // If size is even 
    if (size % 2 == 0) { 
        float median = (float)(arr[(size / 2) - 1] 
                               + arr[size / 2]) 
                       / 2; 
        return median; 
    } 
  
    // If size is odd 
    float median = arr[size / 2]; 
    return median; 
} 
  
// Driver code 
int main() 
{ 
    int arr[] = { 3, 2, 3, 4, 2 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int k = 2; 
    cout << getMaxMedian(arr, n, k); 
  
    return 0; 
} 

Java

import java.util.*; 
  
// Java implementation of the approach 
class GFG  
{ 
  
    // Function to return the maximized median 
    static double getMaxMedian(int[] arr, int n, int k)  
    { 
        int size = n + k; 
  
        // Sort the array 
        Arrays.sort(arr); 
  
        // If size is even 
        if (size % 2 == 0) 
        { 
            double median = (double) (arr[(size / 2) - 1] 
                    + arr[size / 2]) 
                    / 2; 
            return median; 
        } 
  
        // If size is odd 
        double median1 = arr[size / 2]; 
        return median1; 
    } 
  
    // Driver code 
    public static void main(String[] args)  
    { 
        int[] arr = {3, 2, 3, 4, 2}; 
        int n = arr.length; 
        int k = 2; 
        System.out.print((int)getMaxMedian(arr, n, k)); 
  
    } 
} 
  
/* This code contributed by PrinciRaj1992 */

Python3

# Python 3 implementation of the approach 
  
# Function to return the maximized median 
def getMaxMedian(arr, n, k): 
    size = n + k 
  
    # Sort the array 
    arr.sort(reverse = False) 
  
    # If size is even 
    if (size % 2 == 0): 
        median = (arr[int(size / 2) - 1] + 
                  arr[int(size / 2)]) / 2
        return median 
  
    # If size is odd 
    median = arr[int(size / 2)] 
    return median 
  
# Driver code 
if __name__ == '__main__': 
    arr = [3, 2, 3, 4, 2] 
    n = len(arr) 
    k = 2
    print(getMaxMedian(arr, n, k)) 
  
# This code is contributed by 
# Surendra_Gangwar 

C#

// C# implementation of the approach 
using System; 
using System.Linq; 
  
class GFG 
{ 
      
// Function to return the maximized median 
static double getMaxMedian(int []arr, int n, int k) 
{ 
    int size = n + k; 
  
    // Sort the array 
    Array.Sort(arr); 
  
    // If size is even 
    if (size % 2 == 0) 
    { 
        double median = (double)(arr[(size / 2) - 1] 
                            + arr[size / 2]) 
                    / 2; 
        return median; 
    } 
  
    // If size is odd 
    double median1 = arr[size / 2]; 
    return median1; 
} 
  
// Driver code 
static void Main() 
{ 
    int []arr = { 3, 2, 3, 4, 2 }; 
    int n = arr.Length; 
    int k = 2; 
    Console.WriteLine(getMaxMedian(arr, n, k)); 
} 
} 
  
// This code is contributed by mits 

PHP

<?php 
// PHP implementation of the approach 
// Function to return the maximized median 
function getMaxMedian($arr, $n, $k) 
{ 
    $size = $n + $k; 
  
    // Sort the array 
    sort($arr, $n); 
  
    // If size is even 
    if ($size % 2 == 0) 
    { 
        $median = (float)($arr[($size / 2) - 1] + 
                          $arr[$size / 2]) / 2; 
        return $median; 
    } 
  
    // If size is odd 
    $median = $arr[$size / 2]; 
    return $median; 
} 
  
// Driver code 
$arr = array( 3, 2, 3, 4, 2 ); 
$n = sizeof($arr); 
$k = 2; 
echo(getMaxMedian($arr, $n, $k)); 
  
// This code is Contributed by Code_Mech. 

Javascript

<script> 
  
// JavaScript implementation of the approach 
  
// Function to return the maximized median 
function getMaxMedian(arr, n, k) { 
    let size = n + k; 
  
    // Sort the array 
    arr.sort((a, b) => a - b); 
  
    // If size is even 
    if (size % 2 == 0) { 
        let median = (arr[(Math.floor(size / 2) - 1)] +  
        arr[(Math.floor(size / 2))]) / 2; 
        return median; 
    } 
  
    // If size is odd 
    let median = arr[(Math.floor(size / 2))]; 
    return median; 
} 
  
// Driver code 
  
let arr = [3, 2, 3, 4, 2]; 
let n = arr.length; 
let k = 2; 
document.write(getMaxMedian(arr, n, k)); 
  
  
// This code is contributed by _saurabh_jaiswal 
  
</script>

Output

Time Complexity: O(N * logN)
Auxiliary Space: 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!