Difficulty: Cakewalk
Prerequisites: None
Problem:
You’re given an Array A of size N and K the number of extra elements you can insert in the array. You have to find the greatest median you can get after adding exactly K elements to the array.
Explanation:
As K is guaranteed to be less than N and N + K is also guaranteed to be odd, this problem can be solved by first sorting the array and then printing the element at (N + K) / 2 position of the array(For 0 based indexing of Arrays). As the total number of elements you can add is K, then the total size of the modified array will be N + K. And in order to get the largest possible median, all the elements you add should be greater than the max element in the original Array provided. So all the elements come after max element of the array N. Now after sorting the array. The element which is in the middle is at (N + K) / 2 position of the array, which is the largest median possible after adding K new elements to the Array.
My Accepted Solution:
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
*
* @author Vatsal Sura
*/
class ChefAndEmploymentTest {
/**
* @param args the command line arguments
* @throws java.io.IOException
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
for (int n = 0; n < N; n++) {
arr[n] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
System.out.println(arr[(N + K) / 2]);
}
}
}