Minimum number to make median X

 

Minimum number to make median X

Given an unsorted array A[] of distinct integers and size N, and an element X, you need to find the Minimum Number of Elements required to be added to this array so the new median of array becomes X.
Median of array is middle element of array in its sorted form. For odd number of elements N it is the element at position (N-1)/2. For even number of elements N, it is (A[N/2] + A[(N/2) - 1])/2.

Input: The first line contains number of testcases T. Every testcase consists of 2 lines, first line contains N - no of element of arrays and X, and second line contains Array elements in unsorted manner.

Output: You need to find total number of elements to be added to array so that the new median becomes equal to X.

Constraints:
1 <= T <= 100
1 <= N <= 10⁶
1 <= X <= 10⁶
1 <= A[i] <= 10⁶

Example: 
Input: 
2
6 30
10 20 30 100 150 200
5 50
10 20 30 100 150
Output: 
1
1

Explanation: 
Testcase 1: Only 1 element before 30 is required to be added to the array, to make median of array 30.
Testcase 2: Only 1 element between 30 and 100 , i.e number 70 is required to be added to make median 50.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    //code
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,mn=INT_MAX,mx=INT_MIN,gm=0,lm=0,e=0;
        scanf("%d%d",&n,&m);
        int a;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&a);
            if(a==m)
            {
                e=1;
                continue;
            }else if(a>m)
            {
                ++gm;
                mn=min(mn,a);
               
            }else if(a<m)
            {
                ++lm;
                mx=max(mx,a);
            }
        }
      int res=abs(gm-lm),res1=0;
      if(e||mn+mx==2*m)
      {
          cout<<res<<endl;
      }else{
          if(mn+mx<2*m)
          {
              res1=abs(gm-lm-1);
          }else{
              res1=abs(gm-lm+1);
          }
          cout<<min(res+1,res1+1)<<endl;
         
      }
           
    }
    return 0;
}
 

---------------------------------------------------------------------------------------------------------------------------------------

#include <bits/stdc++.h>
using namespace std;

int main() {
   //  ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
	int T;
	cin>>T;
	while(T--){
	    int num, x;
	    cin>>num>>x;
	    int arr[num];
	    for(int i = 0; i<num; i++)
	        cin>>arr[i];
	     
	    int e = 0, l = 0, h = 0;
	    int greatest_smaller = INT_MIN;
	    int smallest_greater = INT_MAX;
	    for(int i = 0; i<num; i++){
	        if(arr[i] == x)
	            e++;
	        else if(arr[i] < x){
	            l++;
	            greatest_smaller = max(greatest_smaller, arr[i]);
	        }
	        else{
	            h++;
	            smallest_greater = min(smallest_greater, arr[i]);
	        }
	    }
	    
	    int to_add = 0;
	    if(num % 2 == 0){
	        to_add = abs(h -l) - e +1;
	        if(e!= 1 && greatest_smaller + smallest_greater == 2*x)
	            to_add--;
	    }
	    else{
	        if(e == 1 || greatest_smaller + smallest_greater == 2*x)
	            to_add = abs(h - l);
	        else if(greatest_smaller + smallest_greater > 2*x){
	            if(l < h)
	                to_add = h - l + 1;
	            else
	                to_add = l - h;
	        }
	        else{
	            if(l < h)
	                to_add = h - l;
	            else
	                to_add = l - h + 1;
	        }
	    }
	    cout<<to_add<<"\n";
	}
}

 

---------------------------------------------------------------------------------------------------------------------------------------

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG
{
    public static void main(String args[])throws IOException
    {
        // Scanner sc = new Scanner(System.in);
        // int t = sc.nextInt();
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(read.readLine());
        
        while(t-- > 0)
        {
            int num = 0, x = 0;
            // num = sc.nextInt();
            // x = sc.nextInt();
            
            String s = read.readLine();
            String st[] = s.trim().split("\\s+");
            num = Integer.parseInt(st[0]);
            x = Integer.parseInt(st[1]);
            
            int arr[] = new int[num];
            
            String str = read.readLine();
            String a[] = str.trim().split("\\s+");
            for(int i = 0; i < num; i++)
            {
                arr[i] = Integer.parseInt(a[i]);
            }
            
            int e = 0, l = 0, h = 0;
	        int greatest_smaller = Integer.MIN_VALUE;
	        int smallest_greater = Integer.MAX_VALUE;
	      for(int i = 0; i< num; i++){
	        if(arr[i] == x)
	            e++;
	        else if(arr[i] < x){
	            l++;
	            greatest_smaller = Math.max(greatest_smaller, arr[i]);
	        }
	        else{
	            h++;
	            smallest_greater = Math.min(smallest_greater, arr[i]);
	        }
	    }
	       int to_add = 0;
	    if(num % 2 == 0){
	        to_add = Math.abs(h -l) - e +1;
	        if(e!= 1 && greatest_smaller + smallest_greater == 2*x)
	            to_add--;
	    }
	    else{
	        if(e == 1 || greatest_smaller + smallest_greater == 2*x)
	            to_add = Math.abs(h - l);
	        else if(greatest_smaller + smallest_greater > 2*x){
	            if(l < h)
	                to_add = h - l + 1;
	            else
	                to_add = l - h;
	        }
	        else{
	            if(l < h)
	                to_add = h - l;
	            else
	                to_add = l - h + 1;
	        }
	    }
	        System.out.println(to_add);
	    
	    
            
        }
    }
}