Dada una array arr[] de tamaño N , la tarea es encontrar el XOR bit a bit de todos los posibles pares desordenados de la array dada .
Ejemplos:
Entrada : arr[] = {1, 5, 3, 7}
Salida: 7
Explicación:
Todos los pares desordenados posibles son (1, 5), (1, 3), (1, 7), (5, 3), ( 5, 7), (3, 7)
Bitwise O de todos los pares posibles son = { ( 1 | 5 ) | ( 1 | 3 ) | ( 1 | 7 ) | ( 5 | 3 ) | ( 5 | 7 ) | ( 3 | 7 ) }
Por lo tanto, la salida requerida es 7.Entrada: arr[] = {4, 5, 12, 15}
Salida: 15
Enfoque: El enfoque más simple para resolver este problema es recorrer la array y generar todos los pares posibles de la array dada . Finalmente, imprima el OR bit a bit de cada elemento de todos los pares posibles de la array dada. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos totalOR, para almacenar Bit-wise OR de cada elemento de todos los pares posibles.
- Recorra la array dada y genere todos los pares posibles (arr[i], arr[j]) a partir de la array dada y para cada par (arr[i], arr[j]), actualice el valor de totalOR = (totalOR | arr [i] | arr[j]) .
- Finalmente, imprima el valor de totalOR .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the Bitwise OR of // all possible pairs from the array int TotalBitwiseORPair(int arr[], int N) { // Stores bitwise OR of all // possible pairs from arr[] int totalOR = 0; // Traverse the array and calculate // bitwise OR of all possible pairs for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // Update totalOR totalOR |= (arr[i] | arr[j]); } } // Return Bitwise OR of all // possible pairs from arr[] return totalOR; } // Driver Code int main() { int arr[] = { 4, 5, 12, 15 }; int N = sizeof(arr) / sizeof(arr[0]); cout << TotalBitwiseORPair(arr, N); }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the Bitwise OR of // all possible pairs from the array static int TotalBitwiseORPair(int arr[], int N) { // Stores bitwise OR of all // possible pairs from arr[] int totalOR = 0; // Traverse the array and // calculate bitwise OR of // all possible pairs for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // Update totalOR totalOR |= (arr[i] | arr[j]); } } // Return Bitwise OR of all // possible pairs from arr[] return totalOR; } // Driver Code public static void main(String[] args) { int arr[] = {4, 5, 12, 15}; int N = arr.length; System.out.print(TotalBitwiseORPair(arr, N)); } } // This code is contributed by sanjoy_62
Python3
# Python3 program to implement # the above approach # Function to find the Bitwise # OR of all possible pairs # from the array def TotalBitwiseORPair(arr, N): # Stores bitwise OR of all # possible pairs from arr[] totalOR = 0 # Traverse the array and # calculate bitwise OR of # all possible pairs for i in range(N): for j in range(i + 1, N): # Update totalOR totalOR |= (arr[i] | arr[j]) # Return Bitwise OR of all # possible pairs from arr[] return totalOR # Driver Code if __name__ == '__main__': arr = [4, 5, 12, 15] N = len(arr) print(TotalBitwiseORPair(arr, N)) # This code is contributed by Mohit Kumar 29
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the Bitwise OR of // all possible pairs from the array static int TotalBitwiseORPair(int[] arr, int N) { // Stores bitwise OR of all // possible pairs from arr[] int totalOR = 0; // Traverse the array and // calculate bitwise OR of // all possible pairs for(int i = 0; i < N; i++) { for(int j = i + 1; j < N; j++) { // Update totalOR totalOR |= (arr[i] | arr[j]); } } // Return Bitwise OR of all // possible pairs from arr[] return totalOR; } // Driver Code public static void Main() { int[] arr = { 4, 5, 12, 15 }; int N = arr.Length; Console.WriteLine(TotalBitwiseORPair(arr, N)); } } // This code is contributed by susmitakundugoaldanga
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the Bitwise OR of // all possible pairs from the array function TotalBitwiseORPair(arr, N) { // Stores bitwise OR of all // possible pairs from arr[] let totalOR = 0; // Traverse the array and calculate // bitwise OR of all possible pairs for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { // Update totalOR totalOR |= (arr[i] | arr[j]); } } // Return Bitwise OR of all // possible pairs from arr[] return totalOR; } // Driver Code let arr = [ 4, 5, 12, 15 ]; let N = arr.length; document.write(TotalBitwiseORPair(arr, N)); // This code is contributed by Surbhi Tyagi </script>
15
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar : O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
1 | 1 | 1 | …..(n veces) = 1
0 | 0 | 0 | …..(n veces) = 0
Por lo tanto, (a | a | a | …. (n veces)) = a
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, diga totalOR para almacenar el OR bit a bit de todos los posibles pares desordenados de la array.
- Recorra la array y actualice el valor de totalOR = (totalOR | arr[i]).
- Finalmente, imprima el valor de totalOR .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the bitwise OR of // all possible pairs of the array int TotalBitwiseORPair(int arr[], int N) { // Stores bitwise OR of all // possible pairs of arr[] int totalOR = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Update totalOR totalOR |= arr[i]; } // Return bitwise OR of all // possible pairs of arr[] return totalOR; } // Driver Code int main() { int arr[] = { 4, 5, 12, 15 }; int N = sizeof(arr) / sizeof(arr[0]); cout << TotalBitwiseORPair(arr, N); }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the bitwise OR of // all possible pairs of the array static int TotalBitwiseORPair(int arr[], int N) { // Stores bitwise OR of all // possible pairs of arr[] int totalOR = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // Update totalOR totalOR |= arr[i]; } // Return bitwise OR of all // possible pairs of arr[] return totalOR; } // Driver Code public static void main(String[] args) { int arr[] = { 4, 5, 12, 15 }; int N = arr.length; System.out.print(TotalBitwiseORPair(arr, N)); } } // This code is contributed by gauravrajput1
Python3
# Python program to implement # the above approach # Function to find the bitwise OR of # all possible pairs of the array def TotalBitwiseORPair(arr, N): # Stores bitwise OR of all # possible pairs of arr totalOR = 0; # Traverse the array arr for i in range(N): # Update totalOR totalOR |= arr[i]; # Return bitwise OR of all # possible pairs of arr return totalOR; # Driver Code if __name__ == '__main__': arr = [4, 5, 12, 15]; N = len(arr); print(TotalBitwiseORPair(arr, N)); # This code is contributed by shikhasingrajput
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the bitwise OR of // all possible pairs of the array static int TotalBitwiseORPair(int []arr, int N) { // Stores bitwise OR of all // possible pairs of []arr int totalOR = 0; // Traverse the array []arr for(int i = 0; i < N; i++) { // Update totalOR totalOR |= arr[i]; } // Return bitwise OR of all // possible pairs of []arr return totalOR; } // Driver Code public static void Main(String[] args) { int []arr = { 4, 5, 12, 15 }; int N = arr.Length; Console.Write(TotalBitwiseORPair(arr, N)); } } // This code is contributed by Princi Singh
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the bitwise OR of // all possible pairs of the array function TotalBitwiseORPair(arr, N) { // Stores bitwise OR of all // possible pairs of arr[] let totalOR = 0; // Traverse the array arr[] for(let i = 0; i < N; i++) { // Update totalOR totalOR |= arr[i]; } // Return bitwise OR of all // possible pairs of arr[] return totalOR; } // Driver Code let arr = [ 4, 5, 12, 15 ]; let N = arr.length; document.write(TotalBitwiseORPair(arr, N)); </script>
15
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA