Check if MEX of an Array can be changed with atmost one Subarray replacement
Given an array arr[] of size N, the task is to check if can you change the MEX of the array to MEX + 1 by replacing at most one subarray with any positive integer. Follow 0-based indexing.
Note: The MEX of the array is the smallest non-negative number that is not present in the array.
Examples:
Input: arr[] = {1, 5, 0, 2, 1}
Output: YES
Explanation: Choose subarray [1, 1](0-based indexing) and change all elements to 3. Now the MEX of the array is 4.Input: arr[] = {1, 4, 0, 2, 4}
Output: NO
Explanation: Initially mex is 3, so we have to remove all occ of 4, After removing, arr = {1}, replacing it with 3 will not increase the MEX by 1.
Approach: To solve the problem follow the below idea:
Let the MEX of the array is x before performing the operation. So, after performing the operation the MEX of the array should be x+1.This means it should contain x at least once and it should not contain x+1.There will be two ways:
- If x+1 is present, then you have to choose a subarray that contains all occ of x+1 and change all its element x.
- If x+1 isn’t present, then you can choose any element from the array such that if we remove it, then the MEX is still the same. and change that element to x
Illustration:
For a better understanding, follow the below illustration:
Consider arr[] = {1, 5, 0, 2, 1 }
- Initially the mex of the array is 3, so after performing an operation the MEX should be 4.
- we will choose subarray [1, 1] (0-based indexing), and change all subarray elements to 3.
- After performing an operation, the array become {1, 3, 0, 2, 1 }.
- Now the MEX of the arr = {1, 3, 0, 2, 1 } is 4. So the MEX is 3+1 = 4.
- So, finally print “YES“.
Below are the steps to implement the above idea:
- Initially, find the mex of the array, let mex is x, and check if can we perform an operation such that after performing an operation, the MEX of the array is x+1.
- If the x + 1 is present in the array, then choose a subarray that contains all x + 1 elements and change all its elements to x.
- If the x + 1 isn’t present in the array, then choose any element such that if we remove it, then the MEX is still the same. and change that element to x.
- In the end, check if the MEX of the resultant is x + 1, if it is x + 1, then print “YES“, else print “NO“.
Below is the implementation of the above approach.
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Funtion to check can you change the // MEX of the array from x to x+1 by // doing a single operation void IncreaseMEX( int * arr, int n) { map< int , int > m; int temp[n]; for ( int i = 0; i < n; i++) { m[arr[i]]++; temp[i] = arr[i]; } // Sorting copy array sort(temp, temp + n); int mx; // Finding mex of the array for ( int i = 0; i < n; i++) { // Using binary search // stl function if (binary_search(temp, temp + n, i)) { // To check element is present // in the array mx = i + 1; continue ; } else { mx = i; break ; } } if (binary_search(temp, temp + n, mx + 1)) { int firstocc, lastocc; for ( int i = 0; i < n; i++) { if (arr[i] == mx + 1) { firstocc = i; break ; } } for ( int i = n - 1; i >= 0; i--) { if (arr[i] == mx + 1) { lastocc = i; break ; } } for ( int i = firstocc; i <= lastocc; i++) { arr[i] = mx; } } else { for ( int i = 0; i < n; i++) { if (arr[i] < mx && m[arr[i]] > 1) { arr[i] = mx; break ; } else if (arr[i] > mx) { arr[i] = mx; break ; } } } // Sort the array for finding MEX // of the resulant array sort(arr, arr + n); int mx1; // Finding MEX of the resulant array for ( int i = 0; i < n; i++) { if (binary_search(arr, arr + n, i)) { mx1 = i + 1; continue ; } else { mx1 = i; break ; } } // If after performing an operation, // the MEX is increase if (mx1 == mx + 1) { // by 1 cout << "YES" << endl; } else { cout << "NO" << endl; } } // Driver code int main() { int arr[] = { 1, 5, 0, 2, 1 }; int n = sizeof (arr) / sizeof ( int ); // Function call IncreaseMEX(arr, n); return 0; } |
Java
import java.util.Arrays; import java.util.Map; import java.util.TreeMap; class GFG { // Function to check if you can change the MEX of the array // from x to x+1 by doing a single operation static void increaseMEX( int [] arr, int n) { Map<Integer, Integer> m = new TreeMap<>(); int [] temp = Arrays.copyOf(arr, n); for ( int i = 0 ; i < n; i++) { m.put(arr[i], m.getOrDefault(arr[i], 0 ) + 1 ); } // Nikunj Sonigara // Sorting copy array Arrays.sort(temp); int mx = 0 ; // Finding MEX of the array for ( int i = 0 ; i < n; i++) { // Using binary search // Arrays.binarySearch returns -(insertion point) - 1 if not found if (Arrays.binarySearch(temp, i) >= 0 ) { // To check if element is present in the array mx = i + 1 ; continue ; } else { mx = i; break ; } } if (Arrays.binarySearch(temp, mx + 1 ) >= 0 ) { int firstOcc = 0 , lastOcc = 0 ; for ( int i = 0 ; i < n; i++) { if (arr[i] == mx + 1 ) { firstOcc = i; break ; } } for ( int i = n - 1 ; i >= 0 ; i--) { if (arr[i] == mx + 1 ) { lastOcc = i; break ; } } for ( int i = firstOcc; i <= lastOcc; i++) { arr[i] = mx; } } else { for ( int i = 0 ; i < n; i++) { if (arr[i] < mx && m.get(arr[i]) > 1 ) { arr[i] = mx; break ; } else if (arr[i] > mx) { arr[i] = mx; break ; } } } // Sort the array for finding MEX of the resultant array Arrays.sort(arr); int mx1 = 0 ; // Finding MEX of the resultant array for ( int i = 0 ; i < n; i++) { if (Arrays.binarySearch(arr, i) >= 0 ) { mx1 = i + 1 ; continue ; } else { mx1 = i; break ; } } // If after performing an operation, the MEX is increased by 1 if (mx1 == mx + 1 ) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } public static void main(String[] args) { int [] arr = { 1 , 5 , 0 , 2 , 1 }; int n = arr.length; // Function call increaseMEX(arr, n); } } |
Python3
# Python code for the above approach # Function to check if you can change the # MEX of the array from x to x+1 by # doing a single operation def increase_mex(arr, n): m = {} temp = [] # Count frequency of each element and create a copy of the array for i in range (n): m[arr[i]] = m.get(arr[i], 0 ) + 1 temp.append(arr[i]) # Sorting the copy array temp.sort() mx = None # Finding MEX of the array for i in range (n): if i in temp: mx = i + 1 else : mx = i break if mx + 1 in temp: # If mx+1 is present in the array first_occ = None last_occ = None # Finding the first and last occurrences of mx+1 for i in range (n): if arr[i] = = mx + 1 : first_occ = i break for i in range (n - 1 , - 1 , - 1 ): if arr[i] = = mx + 1 : last_occ = i break # Changing elements in the range [first_occ, last_occ] to mx for i in range (first_occ, last_occ + 1 ): arr[i] = mx else : for i in range (n): if arr[i] < mx and m[arr[i]] > 1 : arr[i] = mx break elif arr[i] > mx: arr[i] = mx break # Sort the array to find the MEX of the resultant array arr.sort() mx1 = None # Finding MEX of the resultant array for i in range (n): if i in arr: mx1 = i + 1 else : mx1 = i break # If after performing an operation, the MEX is increased by 1 if mx1 = = mx + 1 : print ( "YES" ) else : print ( "NO" ) # Driver code if __name__ = = "__main__" : arr = [ 1 , 5 , 0 , 2 , 1 ] n = len (arr) # Function call increase_mex(arr, n) |
C#
// C# code for the above approach: using System; using System.Collections.Generic; class GFG { // Function to check if you can change the MEX of the array // from x to x+1 by doing a single operation static void IncreaseMEX( int [] arr, int n) { SortedDictionary< int , int > m = new SortedDictionary< int , int >(); int [] temp = new int [n]; Array.Copy(arr, temp, n); for ( int i = 0; i < n; i++) { if (m.ContainsKey(arr[i])) m[arr[i]]++; else m[arr[i]] = 1; } // Sorting copy array Array.Sort(temp); int mx = 0; // Finding MEX of the array for ( int i = 0; i < n; i++) { // Using binary search // Array.BinarySearch returns index of the element if found, // otherwise returns a negative value indicating the insertion point if (Array.BinarySearch(temp, i) >= 0) { // To check if the element is present in the array mx = i + 1; continue ; } else { mx = i; break ; } } if (Array.BinarySearch(temp, mx + 1) >= 0) { int firstOcc = 0, lastOcc = 0; for ( int i = 0; i < n; i++) { if (arr[i] == mx + 1) { firstOcc = i; break ; } } for ( int i = n - 1; i >= 0; i--) { if (arr[i] == mx + 1) { lastOcc = i; break ; } } for ( int i = firstOcc; i <= lastOcc; i++) { arr[i] = mx; } } else { for ( int i = 0; i < n; i++) { if (arr[i] < mx && m[arr[i]] > 1) { arr[i] = mx; break ; } else if (arr[i] > mx) { arr[i] = mx; break ; } } } // Sort the array for finding MEX of the resultant array Array.Sort(arr); int mx1 = 0; // Finding MEX of the resultant array for ( int i = 0; i < n; i++) { if (Array.BinarySearch(arr, i) >= 0) { mx1 = i + 1; continue ; } else { mx1 = i; break ; } } // If after performing an operation, the MEX is increased by 1 if (mx1 == mx + 1) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } public static void Main( string [] args) { int [] arr = { 1, 5, 0, 2, 1 }; int n = arr.Length; // Function call IncreaseMEX(arr, n); } } |
Javascript
// Javascript code for the above approach: // Function to check if you can change the MEX of the array // from x to x+1 by doing a single operation function IncreaseMEX(arr, n) { const m = new Map(); const temp = [...arr]; for (let i = 0; i < n; i++) { m.set(arr[i], (m.get(arr[i]) || 0) + 1); } // Sorting copy array temp.sort((a, b) => a - b); let mx; // Finding mex of the array for (let i = 0; i < n; i++) { // Using binary search if (temp.includes(i)) { mx = i + 1; continue ; } else { mx = i; break ; } } if (temp.includes(mx + 1)) { let firstocc, lastocc; for (let i = 0; i < n; i++) { if (arr[i] === mx + 1) { firstocc = i; break ; } } for (let i = n - 1; i >= 0; i--) { if (arr[i] === mx + 1) { lastocc = i; break ; } } for (let i = firstocc; i <= lastocc; i++) { arr[i] = mx; } } else { for (let i = 0; i < n; i++) { if (arr[i] < mx && m.get(arr[i]) > 1) { arr[i] = mx; break ; } else if (arr[i] > mx) { arr[i] = mx; break ; } } } // Sort the array for finding MEX // of the resulant array arr.sort((a, b) => a - b); let mx1; // Finding MEX of the resulant array for (let i = 0; i < n; i++) { if (arr.includes(i)) { mx1 = i + 1; continue ; } else { mx1 = i; break ; } } // If after performing an operation, // the MEX is increased by 1 if (mx1 === mx + 1) { console.log( "YES" ); } else { console.log( "NO" ); } } // Driver code const arr = [1, 5, 0, 2, 1]; const n = arr.length; // Function call IncreaseMEX(arr, n); |
YES
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Contact Us