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