Dado AND bit a bit , OR y XOR de N elementos de una array denotada por a, b, c. La tarea es encontrar los elementos de la array. Si no existe tal array, imprima «-1».
Ejemplos:
Entrada: N = 3, a = 4, b = 6, c = 6.
Salida: {4, 4, 6}
Explicación:
AND bit a bit de array = 4 & 4 & 6 = 4
OR bit a bit de array = 4 | 4 | 6 = 6
Bitwise XOR de array = 4 ^ 4 ^ 6 = 6
Entrada: N = 2, a = 4, b = 6, c = 6.
Salida: -1
Acercarse:
- Para AND bit a bit , si el i -ésimo bit está configurado en a , entonces en la array cada elemento debe tener i -ésimo bit establecido porque incluso si el i -ésimo bit de un elemento es 0 , entonces el bit-ésimo AND de la array dará como resultado que el i -ésimo bit sea 0 .
- En segundo lugar, si el i -ésimo bit no está establecido en a, entonces los valores OR y XOR deben manejarse simultáneamente. Si se establece i -ésimo bit en b , entonces al menos un elemento debe tener i -ésimo bit establecido. Por lo tanto, establezca i -ésimo bit en el único primer elemento de la array.
- Ahora, si el i -ésimo bit se configuró en b , entonces el i -ésimo bit debe verificarse en c . Si ese bit está configurado en c , entonces no hay problema, ya que el i -ésimo bit del primer elemento ya está configurado, por lo que 1 ^ 0 = 1. Si ese bit no está configurado en c, configure el i -ésimo bit del segundo elemento. Ahora, no habrá ningún efecto en b y para c, 1 ^ 1 será 0 .
- Luego, simplemente calcule Bitwise AND, OR y XOR de la array para verificar si es igual o no. Si los resultados no son iguales, entonces la array no es posible; de lo contrario, la array dada es la respuesta.
A continuación se muestra la implementación del enfoque:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the array void findArray(int n, int a, int b, int c) { int arr[n + 1] = {}; // Loop through all bits in number for (int bit = 30; bit >= 0; bit--) { // If bit is set in AND // then set it in every element // of the array int set = a & (1 << bit); if (set) { for (int i = 0; i < n; i++) arr[i] |= set; } // If bit is not set in AND else { // But set in b(OR) if (b & (1 << bit)) { // Set bit position // in first element arr[0] |= (1 << bit); // If bit is not set in c // then set it in second // element to keep xor as // zero for bit position if (!(c & (1 << bit))) { arr[1] |= (1 << bit); } } } } int aa = INT_MAX, bb = 0, cc = 0; // Calculate AND, OR // and XOR of array for (int i = 0; i < n; i++) { aa &= arr[i]; bb |= arr[i]; cc ^= arr[i]; } // Check if values are equal or not if (a == aa && b == bb && c == cc) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } // If not, then array // is not possible else cout << "-1"; } // Driver Code int main() { // Given Bitwise AND, OR, and XOR int n = 3, a = 4, b = 6, c = 6; // Function Call findArray(n, a, b, c); return 0; }
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to find the array static void findArray(int n, int a, int b, int c) { int arr[] = new int[n + 1]; // Loop through all bits in number for(int bit = 30; bit >= 0; bit--) { // If bit is set in AND // then set it in every element // of the array int set = a & (1 << bit); if (set != 0) { for(int i = 0; i < n; i++) arr[i] |= set; } // If bit is not set in AND else { // But set in b(OR) if ((b & (1 << bit)) != 0) { // Set bit position // in first element arr[0] |= (1 << bit); // If bit is not set in c // then set it in second // element to keep xor as // zero for bit position if ((c & (1 << bit)) == 0) { arr[1] |= (1 << bit); } } } } int aa = Integer.MAX_VALUE, bb = 0, cc = 0; // Calculate AND, OR // and XOR of array for(int i = 0; i < n; i++) { aa &= arr[i]; bb |= arr[i]; cc ^= arr[i]; } // Check if values are equal or not if (a == aa && b == bb && c == cc) { for(int i = 0; i < n; i++) System.out.print(arr[i] + " "); } // If not, then array // is not possible else System.out.println("-1"); } // Driver code public static void main(String[] args) { // Given Bitwise AND, OR, and XOR int n = 3, a = 4, b = 6, c = 6; // Function Call findArray(n, a, b, c); } } // This code is contributed by Pratima Pandey
Python3
# Python3 program for # the above approach import sys # Function to find the array def findArray(n, a, b, c): arr = [0] * (n + 1) # Loop through all bits in number for bit in range (30, -1, -1): # If bit is set in AND # then set it in every element # of the array set = a & (1 << bit) if (set): for i in range (n): arr[i] |= set # If bit is not set in AND else : # But set in b(OR) if (b & (1 << bit)): # Set bit position # in first element arr[0] |= (1 << bit) # If bit is not set in c # then set it in second # element to keep xor as # zero for bit position if (not (c & (1 << bit))): arr[1] |= (1 << bit) aa = sys.maxsize bb = 0 cc = 0 # Calculate AND, OR # and XOR of array for i in range (n): aa &= arr[i] bb |= arr[i] cc ^= arr[i] # Check if values are equal or not if (a == aa and b == bb and c == cc): for i in range (n): print (arr[i], end = " ") # If not, then array # is not possible else: print ("-1") # Driver Code if __name__ =="__main__": # Given Bitwise AND, OR, and XOR n = 3 a = 4 b = 6 c = 6 # Function Call findArray(n, a, b, c) # This code is contributed by Chitranayal
C#
// C# program for the above approach using System; class GFG{ // Function to find the array static void findArray(int n, int a, int b, int c) { int []arr = new int[n + 1]; // Loop through all bits in number for(int bit = 30; bit >= 0; bit--) { // If bit is set in AND // then set it in every element // of the array int set = a & (1 << bit); if (set != 0) { for(int i = 0; i < n; i++) arr[i] |= set; } // If bit is not set in AND else { // But set in b(OR) if ((b & (1 << bit)) != 0) { // Set bit position // in first element arr[0] |= (1 << bit); // If bit is not set in c // then set it in second // element to keep xor as // zero for bit position if ((c & (1 << bit)) == 0) { arr[1] |= (1 << bit); } } } } int aa = int.MaxValue, bb = 0, cc = 0; // Calculate AND, OR // and XOR of array for(int i = 0; i < n; i++) { aa &= arr[i]; bb |= arr[i]; cc ^= arr[i]; } // Check if values are equal or not if (a == aa && b == bb && c == cc) { for(int i = 0; i < n; i++) Console.Write(arr[i] + " "); } // If not, then array // is not possible else Console.WriteLine("-1"); } // Driver code public static void Main(String[] args) { // Given Bitwise AND, OR, and XOR int n = 3, a = 4, b = 6, c = 6; // Function Call findArray(n, a, b, c); } } // This code is contributed by gauravrajput1
Javascript
<script> // Javascript program for the above approach // Function to find the array function findArray(n, a, b, c) { let arr = new Array(n + 1); // Loop through all bits in number for (let bit = 30; bit >= 0; bit--) { // If bit is set in AND // then set it in every element // of the array let set = a & (1 << bit); if (set) { for (let i = 0; i < n; i++) arr[i] |= set; } // If bit is not set in AND else { // But set in b(OR) if (b & (1 << bit)) { // Set bit position // in first element arr[0] |= (1 << bit); // If bit is not set in c // then set it in second // element to keep xor as // zero for bit position if (!(c & (1 << bit))) { arr[1] |= (1 << bit); } } } } let aa = Number.MAX_SAFE_INTEGER, bb = 0, cc = 0; // Calculate AND, OR // and XOR of array for (let i = 0; i < n; i++) { aa &= arr[i]; bb |= arr[i]; cc ^= arr[i]; } // Check if values are equal or not if (a == aa && b == bb && c == cc) { for (let i = 0; i < n; i++) document.write(arr[i] + " "); } // If not, then array // is not possible else document.write("-1"); } // Driver Code // Given Bitwise AND, OR, and XOR let n = 3, a = 4, b = 6, c = 6; // Function Call findArray(n, a, b, c); // This code is contributed by gfgking </script>
Producción:
6 4 4
Complejidad de tiempo: O(31*N)
Publicación traducida automáticamente
Artículo escrito por sarthak_eddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA