Dados dos enteros A y B , la tarea es encontrar el tamaño mínimo posible de la array cuyo MEX de la array es A y Bitwise XOR de todos los elementos de la array es B .
Ejemplos:
Entrada: A = 1, B = 1
Salida: 3
Explicación: La array que puede satisfacer la condición dada es {0, 3, 2} que tiene el tamaño mínimo posible, es decir, 3.Entrada: A = 1, B = 999
Salida: 2
Enfoque: El problema dado se puede resolver mediante las siguientes observaciones:
- Como el MEX de la array debe ser A , se deben incluir todos los elementos sobre el rango [0, A – 1] .
- Para hacer el XOR de todos los elementos de la array como B , se deben agregar algunos números enteros a la array que se pueden clasificar en 3 casos. Suponga que la variable currXOR almacena el valor de XOR en el rango [0, A – 1] que se puede calcular utilizando el enfoque que se describe en este artículo .
- Caso 1 donde currXor = B . En este caso, no es necesario sumar números enteros.
- Caso 2 donde currXor^B = A . En este caso, dado que A no se puede agregar a la array, se deben agregar 2 enteros de modo que su XOR sea A .
- En todos los demás casos, se debe agregar 1 entero para hacer que el XOR de la array dada sea B .
Por lo tanto, el problema anterior se puede resolver encontrando el XOR de todos los números del 0 al A-1 y verificando los casos mencionados anteriormente.
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 minimum size
// of array with given MEX and XOR
int minimumSizeArr(int A, int B)
{
int currXor = 0;
// Find the XOR of values from
// 0 to A-1
int reminder = (A - 1) % 4;
// If A is a multiple of 4
if (reminder == 0)
currXor = A - 1;
// If A % 4 gives remainder 1
else if (reminder == 1)
currXor = 1;
// If A % 4 gives remainder 2
else if (reminder == 2)
currXor = A;
// Initializing array size by A
int minSize = A;
// If XOR of all values of array
// is equal to B
if (currXor == B)
return minSize;
// If the required integer to be
// added is equal to A
else if (currXor ^ B == A)
return minSize + 2;
// Else any integer can be added
else
return minSize + 1;
}
// Driver Code
int main()
{
int A = 1;
int B = 999;
cout << minimumSizeArr(A, B);
return 0;
}
Java
// Java program for the above approach
public class GFG {
// Function to find the minimum size
// of array with given MEX and XOR
static int minimumSizeArr(int A, int B)
{
int currXor = 0;
// Find the XOR of values from
// 0 to A-1
int reminder = (A - 1) % 4;
// If A is a multiple of 4
if (reminder == 0)
currXor = A - 1;
// If A % 4 gives remainder 1
else if (reminder == 1)
currXor = 1;
// If A % 4 gives remainder 2
else if (reminder == 2)
currXor = A;
// Initializing array size by A
int minSize = A;
// If XOR of all values of array
// is equal to B
if (currXor == B)
return minSize;
// If the required integer to be
// added is equal to A
else if ((currXor ^ B) == A)
return minSize + 2;
// Else any integer can be added
else
return minSize + 1;
}
// Driver Code
public static void main (String[] args) {
int A = 1;
int B = 999;
System.out.println(minimumSizeArr(A, B));
}
}
// This code is contributed by AnkThon
Python3
# python program for the above approach # Function to find the minimum size # of array with given MEX and XOR def minimumSizeArr(A, B): currXor = 0 # Find the XOR of values from # 0 to A-1 reminder = (A - 1) % 4 # If A is a multiple of 4 if (reminder == 0): currXor = A - 1 # If A % 4 gives remainder 1 elif (reminder == 1): currXor = 1 # If A % 4 gives remainder 2 elif (reminder == 2): currXor = A # Initializing array size by A minSize = A # If XOR of all values of array # is equal to B if (currXor == B): return minSize # If the required integer to be # added is equal to A elif (currXor ^ B == A): return minSize + 2 # Else any integer can be added else: return minSize + 1 # Driver Code if __name__ == "__main__": A = 1 B = 999 print(minimumSizeArr(A, B)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
public class GFG {
// Function to find the minimum size
// of array with given MEX and XOR
static int minimumSizeArr(int A, int B)
{
int currXor = 0;
// Find the XOR of values from
// 0 to A-1
int reminder = (A - 1) % 4;
// If A is a multiple of 4
if (reminder == 0)
currXor = A - 1;
// If A % 4 gives remainder 1
else if (reminder == 1)
currXor = 1;
// If A % 4 gives remainder 2
else if (reminder == 2)
currXor = A;
// Initializing array size by A
int minSize = A;
// If XOR of all values of array
// is equal to B
if (currXor == B)
return minSize;
// If the required integer to be
// added is equal to A
else if ((currXor ^ B) == A)
return minSize + 2;
// Else any integer can be added
else
return minSize + 1;
}
// Driver Code
public static void Main () {
int A = 1;
int B = 999;
Console.WriteLine(minimumSizeArr(A, B));
}
}
// This code is contributed by ihritik
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum size
// of array with given MEX and XOR
function minimumSizeArr(A, B)
{
let currXor = 0;
// Find the XOR of values from
// 0 to A-1
let reminder = (A - 1) % 4;
// If A is a multiple of 4
if (reminder == 0) currXor = A - 1;
// If A % 4 gives remainder 1
else if (reminder == 1) currXor = 1;
// If A % 4 gives remainder 2
else if (reminder == 2) currXor = A;
// Initializing array size by A
let minSize = A;
// If XOR of all values of array
// is equal to B
if (currXor == B) return minSize;
// If the required integer to be
// added is equal to A
else if (currXor ^ (B == A)) return minSize + 2;
// Else any integer can be added
else return minSize + 1;
}
// Driver Code
let A = 1;
let B = 999;
document.write(minimumSizeArr(A, B));
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
2
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koladiyadrashti123 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA