Minimum operations to make the MEX of the given set equal to x
Given a set of n integers, perform minimum number of operations (you can insert/delete elements into/from the set) to make the MEX of the set equal to x (that is given).
Note:- The MEX of a set of integers is the minimum non-negative integer that doesn’t exist in it. For example, the MEX of the set {0, 2, 4} is 1 and the MEX of the set {1, 2, 3} is 0.
Examples :
Input : n = 5, x = 3
0 4 5 6 7
Output : 2
The MEX of the set {0, 4, 5, 6, 7} is 1 which is
not equal to 3. So, we should add 1 and 2 to the
set. After adding 1 and 2, the set becomes
{0, 1, 2, 4, 5, 6, 7} and 3 is the minimum
non-negative integer that doesn't exist in it.
So, the MEX of this set is 3 which is equal to
x i.e. 3. So, the output of this example is 2
as we inserted 1 and 2 in the set.
Input : n = 1, x = 0
1
Output : 0
In this example, the MEX of the given set {1}
is already 0. So, we do not need to perform
any operation. So, the output is 0.
Approach: The approach is to see that in the final set all the elements less than x should exist, x shouldn’t exist and any element greater than x doesn’t matter. So, we will count the number of elements less than x that don’t exist in the initial set and add this to the answer. If x exists we will add 1 to the answer because x should be removed.
Below is the implementation of above approach:
C++
// CPP program to perform minimal number // of operations to make the MEX of the // set equal to the given number x. #include <bits/stdc++.h> using namespace std; // function to find minimum number of // operations required int minOpeartions( int arr[], int n, int x) { int k = x, i = 0; while (n--) { // if the element is less than x. if (arr[n] < x) k--; // if the element equals to x. if (arr[n] == x) k++; } return k; } // driver function int main() { int arr[] = { 0, 4, 5, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); int x = 3; // output cout << minOpeartions(arr, n, x) << endl; } |
Java
// Java program to perform minimal number // of operations to make the MEX of the // set equal to the given number x. import java.io.*; class GFG { // function to find minimum number of // operations required static int minOpeartions( int arr[], int n, int x) { int k = x, i = 0 ; n--; while (n > - 1 ) { // if the element is less than x. if (arr[n] < x) k--; // if the element equals to x. if (arr[n] == x) k++; n--; } return k; } // driver function public static void main(String args[]) { int arr[] = { 0 , 4 , 5 , 6 , 7 }; int n = arr.length; int x = 3 ; // output System.out.println(minOpeartions(arr, n, x)); } } /* This code is contributed by Nikita Tiwari.*/ |
Python
# Python 3 program to perform minimal number # of operations to make the MEX of the # set equal to the given number x. # function to find minimum number of # operations required def minOpeartions(arr, n, x) : k = x i = 0 n = n - 1 while (n> - 1 ) : # if the element is less than x. if (arr[n] < x) : k = k - 1 # if the element equals to x. if (arr[n] = = x) : k = k + 1 n = n - 1 return k # driver function arr = [ 0 , 4 , 5 , 6 , 7 ] n = len (arr) x = 3 # output print ( minOpeartions(arr, n, x)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to perform minimal number // of operations to make the MEX of the // set equal to the given number x. using System; class GFG { // function to find minimum number // of operations required static int minOpeartions( int [] arr, int n, int x) { int k = x; n--; while (n > -1) { // if the element is less // than x. if (arr[n] < x) k--; // if the element equals // to x. if (arr[n] == x) k++; n--; } return k; } // driver function public static void Main() { int [] arr = { 0, 4, 5, 6, 7 }; int n = arr.Length; int x = 3; // output Console.WriteLine( minOpeartions(arr, n, x)); } } // This code is contributed by vt_m. |
Javascript
<script> // Javascript program to perform minimal number // of operations to make the MEX of the // set equal to the given number x. // function to find minimum number of // operations required function minOpeartions(arr, n, x) { let k = x, i = 0; while (n-- > 0) { // if the element is less than x. if (arr[n] < x) k--; // if the element equals to x. if (arr[n] == x) k++; } return k; } let arr = [ 0, 4, 5, 6, 7 ]; let n = arr.length; let x = 3; // output document.write(minOpeartions(arr, n, x)); </script> |
PHP
<?php // PHP program to perform minimal // number of operations to make // the MEX of the set equal to // the given number x. // function to find minimum number // of operations required function minOpeartions( $arr , $n , $x ) { $k = $x ; $i = 0; while ( $n --) { // if the element is // less than x. if ( $arr [ $n ] < $x ) $k --; // if the element equals to x. if ( $arr [ $n ] == $x ) $k ++; } return $k ; } // Driver Code $arr = array (0, 4, 5, 6, 7); $n = count ( $arr ); $x = 3; echo minOpeartions( $arr , $n , $x ) ; // This code is contributed by anuj_67. ?> |
2
Time Complexity: O(n)
Auxiliary Space: O(1)
Contact Us