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
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
