OR bit a bit de la suma de todas las subsecuencias de una array

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *