Minimum number of elements to add to make median equals x
A median in an array with the length of n is an element which occupies position number (n+1)/2 after we sort the elements in the non-decreasing order (the array elements are numbered starting with 1). A median of an array (2, 6, 1, 2, 3) is the number 2, and a median of array (0, 96, 17, 23) — the number 17.
Examples :
Input : 3 10 10 20 30 Output : 1 In the first sample we can add number 9 to array (10, 20, 30). The resulting array (9, 10, 20, 30) will have a median in position (4+1)/2 = 2, that is, 10 Input : 3 4 1 2 3 Output : 4 In the second sample you should add numbers 4, 5, 5, 5. The resulting array has median equal to 4.
First Approach:- The approach is to add one more number x to the array until the median of the array equals to x. Below is the implementation of the above approach:-
C++
// C++ program to find minimum number // of elements needs to add to the // array so that its median equals x. #include <bits/stdc++.h> using namespace std; // Returns count of elements to be // added to make median x. This function // assumes that a[] has enough extra space. int minNumber( int a[], int n, int x) { // to sort the array in increasing order. sort(a, a + n); int k; for (k = 0; a[(n - 1) / 2] != x; k++) { a[n++] = x; sort(a, a + n); } return k; } // Driver code main() { int x = 10; int a[6] = { 10, 20, 30 }; int n = 3; cout << minNumber(a, n, x) << endl; return 0; } |
Java
// Java program to find minimum number // of elements needs to add to the // array so that its median equals x. import java.util.Arrays; class GFG { // Returns count of elements to be // added to make median x. This function // assumes that a[] has enough extra space. static int minNumber( int a[], int n, int x) { // to sort the array in increasing order. Arrays.sort(a); int k; for (k = 0 ; a[(n) / 2 ] != x; k++) { a[n++] = x; Arrays.sort(a); } return k; } // Driver code public static void main(String[] args) { int x = 10 ; int a[] = { 10 , 20 , 30 }; int n = 3 ; System.out.println(minNumber(a, n- 1 , x)); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 program to find minimum number # of elements needs to add to the # array so that its median equals x. # Returns count of elements to be added # to make median x. This function # assumes that a[] has enough extra space. def minNumber(a, n, x): # to sort the array in increasing order. a.sort(reverse = False ) k = 0 while (a[ int ((n - 1 ) / 2 )] ! = x): a[n - 1 ] = x n + = 1 a.sort(reverse = False ) k + = 1 return k # Driver code if __name__ = = '__main__' : x = 10 a = [ 10 , 20 , 30 ] n = 3 print (minNumber(a, n, x)) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to find minimum number // of elements needs to add to the // array so that its median equals x. using System; class GFG { // Returns count of elements to be // added to make median x. This function // assumes that a[] has enough extra space. static int minNumber( int []a, int n, int x) { // to sort the array in increasing order. Array.Sort(a); int k; for (k = 0; a[(n) / 2] != x; k++) { a[n++] = x; Array.Sort(a); } return k; } // Driver code public static void Main(String[] args) { int x = 10; int []a = { 10, 20, 30 }; int n = 3; Console.WriteLine(minNumber(a, n-1, x)); } } // This code contributed by Rajput-Ji |
PHP
<?php // PHP program to find minimum // number of elements needs to // add to the array so that its // median equals x. // Returns count of elements // to be added to make median // x. This function assumes // that a[] has enough extra space. function minNumber( $a , $n , $x ) { // to sort the array in // increasing order. sort( $a ); $k ; for ( $k = 0; $a [( $n - 1) / 2] != $x ; $k ++) { $a [ $n ++] = $x ; sort( $a ); } return $k ; } // Driver code $x = 10; $a = array (10, 20, 30); $n = 3; echo minNumber( $a , $n , $x ), "\n" ; // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to find minimum number // of elements needs to add to the // array so that its median equals x. // Returns count of elements to be // added to make median x. This function // assumes that a[] has enough extra space. function minNumber(a, n, x) { // to sort the array in increasing order. a.sort(); let k; for (k = 0; a[parseInt((n - 1) / 2, 10)] != x; k++) { a[n++] = x; a.sort(); } return k; } let x = 10; let a = [ 10, 20, 30 ]; let n = 3; document.write(minNumber(a, n, x)); // This code is contributed by mukesh07. </script> |
Output :
1
Time complexity : O(k n Logn)
Auxiliary Space: O(1)
Second Approach:- Better approach is to count all the elements equal to x(that is e), greater than x(that is h) and smaller than x(that is l). And then –
if l is greater than h then, the ans will be (l – h) + 1 – e;
And if h is greater than l then, ans will be (h – l – 1) + 1 – e;
We can use Hoare’s partition scheme to count smaller, equal and greater elements.
Below is the implementation of the above approach:
C++
// C++ program to find minimum number of // elements to add so that its median // equals x. #include <bits/stdc++.h> using namespace std; int minNumber( int a[], int n, int x) { int l = 0, h = 0, e = 0; for ( int i = 0; i < n; i++) { // no. of elements equals to x, // that is, e. if (a[i] == x) e++; // no. of elements greater than x, // that is, h. else if (a[i] > x) h++; // no. of elements smaller than x, // that is, l. else if (a[i] < x) l++; } int ans = 0; if (l > h) ans = l - h; else if (l < h) ans = h - l - 1; // subtract the no. of elements // that are equal to x. return ans + 1 - e; } // Driver code int main() { int x = 10; int a[] = { 10, 20, 30 }; int n = sizeof (a) / sizeof (a[0]); cout << minNumber(a, n, x) << endl; return 0; } |
Java
// Java program to find minimum number // of elements to add so that its // median equals x. import java.util.*; import java.lang.*; class GFG { public static int minNumber( int a[], int n, int x) { int l = 0 , h = 0 , e = 0 ; for ( int i = 0 ; i < n; i++) { // no. of elements equals to // x, that is, e. if (a[i] == x) e++; // no. of elements greater // than x, that is, h. else if (a[i] > x) h++; // no. of elements smaller // than x, that is, l. else if (a[i] < x) l++; } int ans = 0 ; if (l > h) ans = l - h; else if (l < h) ans = h - l - 1 ; // subtract the no. of elements // that are equal to x. return ans + 1 - e; } // Driven Program public static void main(String[] args) { int x = 10 ; int a[] = { 10 , 20 , 30 }; int n = a.length; System.out.println( minNumber(a, n, x)); } } // This code is contributed by // Prasad Kshirsagar |
Python3
# Python3 program to find minimum number # of elements to add so that its median # equals x. def minNumber (a, n, x): l = 0 h = 0 e = 0 for i in range (n): # no. of elements equals to x, # that is, e. if a[i] = = x: e + = 1 # no. of elements greater than x, # that is, h. elif a[i] > x: h + = 1 # no. of elements smaller than x, # that is, l. elif a[i] < x: l + = 1 ans = 0 ; if l > h: ans = l - h elif l < h: ans = h - l - 1 ; # subtract the no. of elements # that are equal to x. return ans + 1 - e # Driver code x = 10 a = [ 10 , 20 , 30 ] n = len (a) print (minNumber(a, n, x)) # This code is contributed # by "Abhishek Sharma 44" |
C#
// C# program to find minimum // number of elements to add // so that its median equals x. using System; class GFG { public static int minNumber( int []a, int n, int x) { int l = 0, h = 0, e = 0; for ( int i = 0; i < n; i++) { // no. of elements // equals to x, // that is, e. if (a[i] == x) e++; // no. of elements // greater than x, // that is, h. else if (a[i] > x) h++; // no. of elements smaller // than x, that is, l. else if (a[i] < x) l++; } int ans = 0; if (l > h) ans = l - h; else if (l < h) ans = h - l - 1; // subtract the no. // of elements that // are equal to x. return ans + 1 - e; } // Driver Code public static void Main() { int x = 10; int []a = {10, 20, 30}; int n = a.Length; Console.WriteLine( minNumber(a, n, x)); } } // This code is contributed // by anuj_67. |
PHP
<?php // PHP program to find minimum // number of elements to add so // that its median equals x. function minNumber( $a , $n , $x ) { $l = 0; $h = 0; $e = 0; for ( $i = 0; $i < $n ; $i ++) { // no. of elements equals // to x, that is, e. if ( $a [ $i ] == $x ) $e ++; // no. of elements greater // than x, that is, h. else if ( $a [ $i ] > $x ) $h ++; // no. of elements smaller // than x, that is, l. else if ( $a [ $i ] < $x ) $l ++; } $ans = 0; if ( $l > $h ) $ans = $l - $h ; else if ( $l < $h ) $ans = $h - $l - 1; // subtract the no. of elements // that are equal to x. return $ans + 1 - $e ; } // Driver code $x = 10; $a = array (10, 20, 30); $n = sizeof( $a ) ; echo minNumber( $a , $n , $x ), "\n" ; // This code is contributed by jit_t ?> |
Javascript
<script> // Javascript program to find minimum number // of elements to add so that its median // equals x. function minNumber(a, n, x) { let l = 0, h = 0, e = 0; for (let i = 0; i < n; i++) { // No. of elements equals to x, // that is, e. if (a[i] == x) e++; // No. of elements greater than x, // that is, h. else if (a[i] > x) h++; // No. of elements smaller than x, // that is, l. else if (a[i] < x) l++; } let ans = 0; if (l > h) ans = l - h; else if (l < h) ans = h - l - 1; // Subtract the no. of elements // that are equal to x. return ans + 1 - e; } // Driver code let x = 10; let a = [ 10, 20, 30 ]; let n = a.length; document.write(minNumber(a, n, x)); // This code is contributed by suresh07 </script> |
Output :
1
Time complexity : O(n)
Auxiliary Space: O(1)
Contact Us