MEX de secuencia generada de N+1 enteros donde i-ésimo entero es XOR de (i-1) y K

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 8

Entrada: 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:

  1. Genere la secuencia y ordénela.
  2. 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.
  3. 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:

  1. Iterar a través de los bits de N+1 y K desde atrás.
  2. 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.
  3. 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.
  4. 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.
  5. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *