Dados dos números enteros N y K , genere una secuencia de tamaño N+1 donde el i -ésimo elemento sea (i-1)⊕K , la tarea es encontrar el MEX de esta secuencia. Aquí, el MEX de una secuencia es el entero no negativo más pequeño que no ocurre en la secuencia.
Ejemplos:
Entrada : N = 7, K=3
Salida : 8
Explicación: La secuencia formada por N y K dados es {0⊕3, 1⊕3, 2⊕3, 3⊕3, 4⊕3, 5⊕3, 6⊕3 , 7⊕3} es decir, {3, 2, 1, 0, 7, 6, 5, 4}
El número no negativo más pequeño que no está presente en la secuencia dada es 8Entrada: N = 6, K=4
Salida: 3
Enfoque nativo: el enfoque más simple para resolver este problema es simplemente hacer la array de lo dado y calcular su MEX . Los siguientes son los pasos para solucionar este problema:
- Genere la secuencia y ordénela.
- Inicialice MEX a 0 e itere sobre la array ordenada, si el elemento actual es igual a MEX , aumente MEX en 1; de lo contrario, rompa el ciclo.
- Escriba MEX como la respuesta a este problema.
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Enfoque eficiente: si un número M está ocurriendo en esta secuencia, entonces para algún i -ésimo término (i-1)⊕K = M , lo que también significa M⊕K = (i-1) , donde el valor máximo de ( i-1 ) es N . Ahora, suponga que X es el MEX de la secuencia dada, entonces X⊕K debe ser mayor que N , es decir, X⊕K > N. Entonces, el valor mínimo de X es el MEX de la secuencia. Siga los pasos a continuación para resolver este problema:
- Iterar a través de los bits de N+1 y K desde atrás.
- Si el i -ésimo bit de K es igual al i -ésimo bit de N+1, establezca el i -ésimo bit de X en 0.
- Si el i -ésimo bit de K es igual a 0 y el i -ésimo bit de N+1 es igual a 1, establezca el i -ésimo bit de X en 1.
- Si el i -ésimo bit de K es igual a 1 y el i -ésimo bit de N+1 es igual a 0 , establezca todos los bits inferiores restantes de X en 0 porque esto significa que el número que contiene un bit establecido en esta posición es falta y es el MEX de la secuencia.
- Escriba la respuesta de acuerdo con la observación anterior.
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de tiempo: O(log(max(N, K))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nebula_242 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA