Encuentre OR bit a bit de todos los sub-arreglos posibles

Dada una array A de tamaño N donde,  . La tarea es encontrar el OR de todos los subconjuntos posibles de A y luego el OR de todos estos resultados.
Ejemplos: 
 

Input : 1 4 6
Output : 7
All possible subarrays are 
{1}, {1, 4}, {4, 6} and {1, 4, 6}
ORs of these subarrays are 1, 5, 6
and 7. OR of these ORs is 7.

Input : 10 100 1000
Output : 1006

Enfoque: En el SET 1 hemos visto cómo encontrar AND bit a bit de todos los subarreglos posibles. Un enfoque similar también es aplicable aquí.
La solución Naive es encontrar el OR de todos los subconjuntos y luego generar el OR de sus resultados. Esto conducirá a la solución O(N ^{2 ).}
Solución Eficiente: Usando la propiedad que  i:e no importa cuantas veces venga un elemento, su ORing será contado como uno solo. Por tanto, nuestro problema se reduce a encontrar el OR de todos los elementos del arreglo.
A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program to find OR of all the sub-arrays
#include <bits/stdc++.h>
using namespace std;
 
// function to return OR of sub-arrays
int OR(int a[], int n)
{
    int ans = a[0];
    for (int i = 1; i < n; ++i)
         ans |= a[i];   
 
    return ans;
}
 
// Driver program
int main()
{
    int a[] = { 1, 4, 6 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // print OR of all subarrays
    cout << OR(a, n);
 
    return 0;
}

// Java program to find OR of
// all the sub-arrays
class GFG
{
     
// function to return OR
// of sub-arrays
static int OR(int a[],int n)
{
    int ans = a[0];
    int i;
    for(i = 1; i < n; i++)
    {
        ans |= a[i];
    }
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
    int a[] = { 1, 4, 6};
     
    int n = a.length;
     
    // print OR of all subarrays
    System.out.println(OR(a, n));
}
}
 
// This code is contributed
// by ANKITRAI1

# Python3 program to find OR of all the sub-arrays
 
# function to return OR of sub-arrays
def OR(a, n):
     
    ans = a[0]
    for i in range(1,n):
        ans |= a[i]
     
    return ans
     
# Driver Code
if __name__=='__main__':
    a = [1, 4, 6]
    n = len(a)
 
# print OR of all subarrays
    print(OR(a, n))
 
# This code is contributed
# by Shashank_Sharma

// C# program to find OR of
// all the sub-arrays
using System;
 
class GFG
{
     
// function to return OR
// of sub-arrays
static int OR(int[] a, int n)
{
    int ans = a[0];
    int i;
    for(i = 1; i < n; i++)
    {
        ans |= a[i];
    }
    return ans;
}
 
// Driver Code
public static void Main()
{
    int[] a = { 1, 4, 6};
     
    int n = a.Length;
     
    // print OR of all subarrays
    Console.Write(OR(a, n));
}
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP program to find OR
// of all the sub-arrays
 
// function to return OR
// of sub-arrays
function O_R($a, $n)
{
    $ans = $a[0];
    for ($i = 1; $i < $n; ++$i)
        $ans |= $a[$i];
 
    return $ans;
}
 
// Driver Code
$a = array( 1, 4, 6 );
$n = count($a);
 
// print OR of all subarrays
echo O_R($a, $n);
 
// This code is contributed
// by inder_verma
?>

<script>
 
// Javascript program to find OR of all the sub-arrays
 
// function to return OR of sub-arrays
function OR(a, n)
{
    var ans = a[0];
    for (var i = 1; i < n; ++i)
         ans |= a[i];   
 
    return ans;
}
 
var a = [ 1, 4, 6 ];
var n = a.length;
 
    // print OR of all subarrays
 document.write(OR(a, n));
 
// This code is contributed by SoumikMondal
 
</script>

Producción:  

7

Complejidad de tiempo: O(N)