Dada una array arr[] de longitud N , la tarea es encontrar el OR bit a bit de la suma de todas las subsecuencias posibles de la array dada.
Ejemplos:
Entrada: arr[] = {4, 2, 5}
Salida: 15
Explicación: Todas las subsecuencias de la array dada y sus sumas correspondientes:
{4} – 4
{2} – 2
{5} – 5
{4, 2} – 6
{4, 5} – 9
{2, 5} – 7
{4, 2, 5} -11
Por lo tanto, el OR bit a bit de todas las sumas = 4 | 2 | 5 | 6 | 9 | 7 | 11 = 15.Entrada: arr[] = {1, 9, 8}
Salida: 27
Explicación: Todas las subsecuencias de la array dada y sus sumas correspondientes:
{1} – 1
{9} – 9
{8} – 8
{1, 9} – 10
{9, 8} – 17
{1, 8} – 9
{1, 9, 8} – 18
Por lo tanto, Bitwise OR de todas las sumas = 1 | 9 | 8 | 10 | 17 | 9 | 18 = 27.
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles a partir de la array dada y encontrar sus respectivas sumas. Ahora, después de calcular sus sumas, imprime el OR Bitwise de todas las sumas obtenidas.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
- Todos los bits establecidos en los elementos de la array también se establecen en el resultado final.
- Todos los bits establecidos en la array de suma de prefijos de la array dada también se establecen en el resultado final.
Siga los pasos a continuación para resolver el problema anterior:
- Inicialice un resultado variable con 0 que almacene el OR bit a bit de la suma de cada subsecuencia de la array dada arr[] .
- Inicialice una variable prefixSum con 0 que almacene la suma del prefijo de arr[] en cualquier instante.
- Iterar sobre los elementos de la array en el rango [0, N] usando la variable i .
- Actualice prefixSum como prefixSum+= arr[i] .
- Actualizar resultado como resultado | = arr[i] | prefijoSuma.
- Después de los pasos anteriores, imprima el valor del resultado como respuesta.
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 calculate Bitwise OR of // sums of all subsequences int findOR(int nums[], int N) { // Stores the prefix sum of nums[] int prefix_sum = 0; // Stores the bitwise OR of // sum of each subsequence int result = 0; // Iterate through array nums[] for (int i = 0; i < N; i++) { // Bits set in nums[i] are // also set in result result |= nums[i]; // Calculate prefix_sum prefix_sum += nums[i]; // Bits set in prefix_sum // are also set in result result |= prefix_sum; } // Return the result return result; } // Driver Code int main() { // Given array arr[] int arr[] = { 4, 2, 5 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << findOR(arr, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to calculate Bitwise OR of // sums of all subsequences static int findOR(int nums[], int N) { // Stores the prefix sum of nums[] int prefix_sum = 0; // Stores the bitwise OR of // sum of each subsequence int result = 0; // Iterate through array nums[] for (int i = 0; i < N; i++) { // Bits set in nums[i] are // also set in result result |= nums[i]; // Calculate prefix_sum prefix_sum += nums[i]; // Bits set in prefix_sum // are also set in result result |= prefix_sum; } // Return the result return result; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 4, 2, 5 }; int N = arr.length; System.out.print(findOR(arr, N)); } }
Python3
# Python3 program for the # above approach # Function to calculate # Bitwise OR of sums of # all subsequences def findOR(nums, N): # Stores the prefix # sum of nums[] prefix_sum = 0 # Stores the bitwise OR of # sum of each subsequence result = 0 # Iterate through array nums[] for i in range(N): # Bits set in nums[i] are # also set in result result |= nums[i] # Calculate prefix_sum prefix_sum += nums[i] # Bits set in prefix_sum # are also set in result result |= prefix_sum # Return the result return result # Driver Code if __name__ == "__main__": # Given array arr[] arr = [4, 2, 5] N = len(arr) # Function Call print(findOR(arr, N)) # This code is contributed by Chitranayal
C#
// C# program for the above approach using System; class GFG{ // Function to calculate Bitwise OR of // sums of all subsequences static int findOR(int[] nums, int N) { // Stores the prefix sum of nums[] int prefix_sum = 0; // Stores the bitwise OR of // sum of each subsequence int result = 0; // Iterate through array nums[] for(int i = 0; i < N; i++) { // Bits set in nums[i] are // also set in result result |= nums[i]; // Calculate prefix_sum prefix_sum += nums[i]; // Bits set in prefix_sum // are also set in result result |= prefix_sum; } // Return the result return result; } // Driver Code public static void Main() { // Given array arr[] int[] arr = { 4, 2, 5 }; // Size of array int N = arr.Length; // Function call Console.Write(findOR(arr, N)); } } // This code is contributed by code_hunt
Javascript
<script> // JavaScript program for the above approach // Function to calculate Bitwise OR of // sums of all subsequences function findOR(nums, N) { // Stores the prefix sum of nums[] let prefix_sum = 0; // Stores the bitwise OR of // sum of each subsequence let result = 0; // Iterate through array nums[] for (let i = 0; i < N; i++) { // Bits set in nums[i] are // also set in result result |= nums[i]; // Calculate prefix_sum prefix_sum += nums[i]; // Bits set in prefix_sum // are also set in result result |= prefix_sum; } // Return the result return result; } // Driver Code // Given array arr[] let arr = [ 4, 2, 5 ]; let N = arr.length; document.write(findOR(arr, N)); // This code is contributed by avijitmondal1998. </script>
15
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA