MEX of generated sequence of N+1 integers where ith integer is XOR of (i-1) and K
Given two integers N and K, generate a sequence of size N+1 where the ith element is (i-1)⊕K, the task is to find the MEX of this sequence. Here, the MEX of a sequence is the smallest non-negative integer that does not occur in the sequence.
Examples:
Input: N = 7, K=3
Output: 8
Explanation: Sequence formed by given N and K is {0⊕3, 1⊕3, 2⊕3, 3⊕3, 4⊕3, 5⊕3, 6⊕3, 7⊕3} i.e {3, 2, 1, 0, 7, 6, 5, 4}
Smallest non-negative number not present in the given sequence is 8Input: N = 6, K=4
Output: 3
Native Approach: The simplest approach to solve this problem is to simply make the array of the given and calculate its MEX. Following are the steps to solve this problem:
- Generate the sequence and sort it.
- Initialize MEX to 0 and iterate over the sorted array, if the current element is equal to MEX increase MEX by 1 otherwise break the loop.
- Print MEX as the answer to this problem.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the MEX of sequence int findMex( int N, int K) { // Generating the sequence int A[N + 1]; for ( int i = 0; i <= N; i++) { A[i] = i ^ K; } // Sorting the array sort(A, A + N + 1); // Calculating the MEX // Initialising the MEX variable int MEX = 0; for ( int x : A) { if (x == MEX) { // If current MEX is equal // to the element // increase MEX by one MEX++; } else { // If current MEX is not equal // to the element then // the current MEX is the answer break ; } } return MEX; } // Driver code int main() { // Given Input int N = 7, K = 3; cout << findMex(N, K); return 0; } |
Java
// Java program to find the Highest // Power of M that divides N import java.util.*; public class GFG { // Function to find the MEX of sequence static int findMex( int N, int K) { // Generating the sequence int [] A = new int [N + 1 ]; for ( int i = 0 ; i <= N; i++) { A[i] = i ^ K; } // Sorting the array Arrays.sort(A); // Calculating the MEX // Initialising the MEX variable int MEX = 0 ; for ( int i = 0 ; i < A.length; i++) { if (A[i] == MEX) { // If current MEX is equal // to the element // increase MEX by one MEX++; } else { // If current MEX is not equal // to the element then // the current MEX is the answer break ; } } return MEX; } // Driver code public static void main(String args[]) { // Given Input int N = 7 , K = 3 ; System.out.println(findMex(N, K)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for the above approach # Function to find the MEX of sequence def findMex(N, K): # Generating the sequence A = [ 0 ] * (N + 1 ) for i in range (N + 1 ): A[i] = i ^ K # Sorting the array A.sort() # Calculating the MEX # Initialising the MEX variable MEX = 0 for x in A: if (x = = MEX): # If current MEX is equal # to the element # increase MEX by one MEX + = 1 else : # If current MEX is not equal # to the element then # the current MEX is the answer break return MEX # Driver code # Given Input N = 7 K = 3 print (findMex(N, K)) # This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approach using System; class GFG{ // Function to find the MEX of sequence static int findMex( int N, int K) { // Generating the sequence int [] A = new int [N + 1]; for ( int i = 0; i <= N; i++) { A[i] = i ^ K; } // Sorting the array Array.Sort(A); // Calculating the MEX // Initialising the MEX variable int MEX = 0; foreach ( int x in A) { if (x == MEX) { // If current MEX is equal // to the element // increase MEX by one MEX++; } else { // If current MEX is not equal // to the element then // the current MEX is the answer break ; } } return MEX; } // Driver code public static void Main() { // Given Input int N = 7, K = 3; Console.WriteLine(findMex(N, K)); } } // This code is contributed by ukasp |
Javascript
<script> // Javascript program for the above approach // Function to find the MEX of sequence function findMex(N, K) { // Generating the sequence let A = new Array(N + 1); for (let i = 0; i <= N; i++) { A[i] = i ^ K; } // Sorting the array A.sort(); // Calculating the MEX // Initialising the MEX variable let MEX = 0; for (x of A) { if (x == MEX) { // If current MEX is equal // to the element // increase MEX by one MEX++; } else { // If current MEX is not equal // to the element then // the current MEX is the answer break ; } } return MEX; } // Driver code // Given Input let N = 7 let K = 3; document.write(findMex(N, K)) // This code is contributed by gfgking. </script> |
8
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Efficient Approach: If a number M is occurring in this sequence then for some ith term (i-1)⊕K = M, which also means M⊕K = (i-1), where the maximum value of (i-1) is N. Now, assume that X is the MEX of the given sequence, then X⊕K must be greater than N, i.e X⊕K > N. So, the minimum value of X is the MEX of the sequence. Follow the below steps, to solve this problem:
- Iterate through the bits of both N+1 and K from backwards.
- If the ith bit of K is equal to the ith bit of N+1, set the ith bit of X to 0.
- If the ith bit of K is equal to 0 and the ith bit of N+1 is equal to 1, set the ith bit of X to 1.
- If the ith bit of K is equal to 1 and the ith bit of N+1 is equal to 0, set all the remaining lower bits of X to 0 because this means that the number which contains a set bit in this position is missing and it is the MEX of the sequence.
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the MEX of the sequence int findMEX( int N, int K) { // Calculating the last possible bit int lastBit = max(round(log2(N + 1)), round(log2(K))); // Initialising X int X = 0; for ( int i = lastBit; i >= 0; i--) { // If the ith bit of K is equal // to the ith bit of N+1 then the // ith bit of X will remain 0 if ((K >> i & 1) == ((N + 1) >> i & 1)) continue ; // If the ith bit of K is equal to 0 // and the ith bit of N+1 is equal to 1, // set the ith bit of X to 1 else if ((K >> i & 1) == 0) X = X | (1 << i); // If the ith bit of K is equal to 1 // and the ith bit of N+1 is equal to 0, // all the remaining bits will // remain unset else break ; } return X; } // Driver Code int main() { // Given Input int N = 6, K = 4; cout << findMEX(N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to calculate the // log base 2 of an integer static int log2( int N) { // calculate log2 N indirectly // using log() method int result = ( int )(Math.log(N) / Math.log( 2 )); return result; } // Function to find the MEX of the sequence static int findMEX( int N, int K) { // Calculating the last possible bit int lastBit = Math.max(Math.round(log2(N + 1 )), Math.round(log2(K))); // Initialising X int X = 0 ; for ( int i = lastBit; i >= 0 ; i--) { // If the ith bit of K is equal // to the ith bit of N+1 then the // ith bit of X will remain 0 if ((K >> i & 1 ) == ((N + 1 ) >> i & 1 )) continue ; // If the ith bit of K is equal to 0 // and the ith bit of N+1 is equal to 1, // set the ith bit of X to 1 else if ((K >> i & 1 ) == 0 ) X = X | ( 1 << i); // If the ith bit of K is equal to 1 // and the ith bit of N+1 is equal to 0, // all the remaining bits will // remain unset else break ; } return X; } // Driver Code public static void main(String args[]) { // Given Input int N = 6 , K = 4 ; System.out.println(findMEX(N, K)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for the above approach from math import * # Function to find the MEX of the sequence def findMEX(N, K): # Calculating the last possible bit lastBit = max ( round (log2(N + 1 )), round (log2(K))) # Initialising X X = 0 for i in range (lastBit, - 1 , - 1 ): # If the ith bit of K is equal # to the ith bit of N+1 then the # ith bit of X will remain 0 if ((K >> i & 1 ) = = ((N + 1 ) >> i & 1 )): continue # If the ith bit of K is equal to 0 # and the ith bit of N+1 is equal to 1, # set the ith bit of X to 1 elif ((K >> i & 1 ) = = 0 ): X = X | ( 1 << i) # If the ith bit of K is equal to 1 # and the ith bit of N+1 is equal to 0, # all the remaining bits will # remain unset else : break return X # Driver Code # Given Input N = 6 K = 4 print (findMEX(N, K)) # This code is contributed by Shubham Singh |
C#
// C# program for the above approach using System; class GFG { // Function to calculate the // log base 2 of an integer static double log2( int N) { // calculate log2 N indirectly // using log() method double result = (Math.Log(N) / Math.Log(2)); return result; } // Function to find the MEX of the sequence static int findMEX( int N, int K) { // Calculating the last possible bit int lastBit = Math.Max(( int )Math.Round(log2(N + 1)), ( int )Math.Round(log2(K))); // Initialising X int X = 0; for ( int i = lastBit; i >= 0; i--) { // If the ith bit of K is equal // to the ith bit of N+1 then the // ith bit of X will remain 0 if ((K >> i & 1) == ((N + 1) >> i & 1)) continue ; // If the ith bit of K is equal to 0 // and the ith bit of N+1 is equal to 1, // set the ith bit of X to 1 else if ((K >> i & 1) == 0) X = X | (1 << i); // If the ith bit of K is equal to 1 // and the ith bit of N+1 is equal to 0, // all the remaining bits will // remain unset else break ; } return X; } // Driver Code public static void Main() { // Given Input int N = 6, K = 4; Console.Write(findMEX(N, K)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for the above approach // Function to find the MEX of the sequence const findMEX = (N, K) => { // Calculating the last possible bit let lastBit = Math.max(Math.round(Math.log2(N + 1)), Math.round(Math.log2(K))); // Initialising X let X = 0; for (let i = lastBit; i >= 0; i--) { // If the ith bit of K is equal // to the ith bit of N+1 then the // ith bit of X will remain 0 if ((K >> i & 1) == ((N + 1) >> i & 1)) continue ; // If the ith bit of K is equal to 0 // and the ith bit of N+1 is equal to 1, // set the ith bit of X to 1 else if ((K >> i & 1) == 0) X = X | (1 << i); // If the ith bit of K is equal to 1 // and the ith bit of N+1 is equal to 0, // all the remaining bits will // remain unset else break ; } return X; } // Driver Code // Given Input let N = 6, K = 4; document.write(findMEX(N, K)); // This code is contributed by rakeshsahni </script> |
3
Time Complexity: O(log(max(N, K))
Auxiliary Space: O(1)
Contact Us