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>
Producción
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>
Producción
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