Maulik is a student in the department of Mathematics and Statistics

Maulik is a student in the department of Mathematics and Statistics. He is working on a properties of a median of a set of numbers.

 

He has set of distinct numbers and he wants to find out K numbers from that set which are closest to the median of the set of numbers.

He wants all these K numbers in ascending order.

The median of the set of number is found by following procedure:

-  Step1 First of all the numbers are sorted in ascending order

-  Step2.1 the total numbers in the set are odd then the median is the middle number in the set.

-  Step2.2 If the total numbers in the set are even then the median is the mean of two middle most numbers.

Design a program which takes set of numbers and value of K as an argument and display K numbers which are closest to the median of the set of numbers. 

Restriction:

-  If while selecting K numbers, if you find two numbers which are equally closest to the median then select the lowest number out of those two numbers. - The numbers must be displayed in ascending order. 

Input

Command Line argument: Value of K <space> List of numbers in the set separated by space Output format:List of K numbers closest to median in ascending order. 

Example

Example 1: 
Input: 2 1 3 5 7 9 
Output 3 5 

Example 2: 
Input: 8 100 1 5 9 105 103 102 104 10 15 106 18 101 
Output: 18 100 101 102 103 104 105 106 

Example 3: 
Input: 5 9 15 27 22 26 1 5 10 24 18  
Output: 9 10 15 18 22 


solution

//Prectical - 1
import java.util.*;
class Main
{
    // Driver code
    public static void main(String args[])
    {
           int n, i, h, l, k , b;
           double d1,d2, median;
           Scanner input= new Scanner(System.in);
           System.out.print("\nK: ");
           k = input.nextInt();
           System.out.print("Enter the number of element in dataset:");
           n = input.nextInt();
        //   int a[n];
           int a[]=new int[n];
           for(i = 0; i < n; i++) {
               b = i+1;
               System.out.print("\nEnter " + b +" element: ");
                a[i] = input.nextInt(); 
            }
            // QuickSort(a, 0, n-1);
            Arrays.sort(a);   
            
            System.out.print("The " + n + " element nearest to the median are: ");
            
            if(n%2 == 1) {
      median = a[n/2];
      h = n/2+1;
      l= n/2;
      while(k > 0) {
         if((median-a[l] <= a[h]-median) && l >= 0) {
             System.out.print(" " + a[l]);
            l--;
            k--;
         } else if((median-a[l] > a[h]-median) && h <= n-1) {
             System.out.print(" " + a[h]);
            h++;
            k--;
         }
      }
   } else {
      d1 = a[n/2];
      d2 = a[n/2-1];
      median = (d1+d2)/2;
      h = n/2;
      l = n/2-1;
      while(k > 0) {
         d1 = a[l];
         d2 = a[h];
         if((median-d2 <= d1-median) && l >= 0) {
             System.out.print(" " + a[l]);
            l--;
            k--;
         } else if((median-d2 > d1-median) && h <= n-1) {
            
             System.out.print(" " + a[h]);
            h++;
            k--;
         }
      }
   }
            
    }
}


/*
K: 2                                                                                                                            
Enter the number of element in dataset:5                                                                                        
                                                                                                                                
Enter 1 element: 1                                                                                                              
Enter 2 element: 3                                                                                                              
Enter 3 element: 5                                                                                                              
Enter 4 element: 7                                                                                                              
Enter 5 element: 9                                                                                                              
The 5 element nearest to the median are:  5 3  
*/