Encuentre AND bit a bit (&) de todos los sub-arreglos posibles

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

Ejemplos: 

Input : 1 2 3
Output : 0
All possible subarrays are 
{1}, {2}, {3}, {1, 2}, {2, 3} and {1, 2, 3}
ANDs of these subarrays are 1, 2, 3, 0, 2, 0.
AND of these ANDs is 0.

Input : 100 500 1000
Output : 96 

Enfoque:
la solución Naive es encontrar el AND de todos los subconjuntos y luego imprimir el AND de sus resultados. Esto conducirá a la solución O(N ^{2 ).}

Solución Óptima: Usando las propiedades de  i:e no importa cuantas veces venga un elemento, su AND se contará como uno solo. Por lo tanto, nuestro problema se reduce a encontrar el AND de todos los elementos de la array solamente.

A continuación se muestra la implementación del enfoque anterior.

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

//Java program to find of all the sub-arrays
public class GFG {
 
    //function to return AND of sub-arrays
    static int AND(int a[], int n)
    {
     int ans = a[0];
     for (int i = 0; i < n; ++i)
         ans &= a[i]; 
     return ans;
    }
 
    // Driver code
    public static void main(String[] args) {
     
        int a[] = { 1, 2, 3 };
 
         // size of the array
         int n = a.length;
 
         // print and of all subarrays
         System.out.println(AND(a, n));
    }
}

# Python 3 Program  to find of all the sub-arrays
 
# function to return AND of sub-arrays
def AND(a, n) :
 
    ans = a[0]
    for i in range(n) :
        ans &= a[i]
         
    return ans
 
 
 
# Driver Code
if __name__ == "__main__" :
 
    a = [ 1, 2, 3]
 
    # size of the array
    n = len(a)
 
    # print and of all subarrays
    print(AND(a, n))
 
# This code is contributed by ANKITRAI1

//C# program to find of all the sub-arrays 
 
using System;
 
public class GFG {
   
    //function to return AND of sub-arrays
    static int AND(int []a, int n)
    {
     int ans = a[0];
     for (int i = 0; i < n; ++i) 
         ans &= a[i];  
     return ans;
    }
   
    // Driver code
    public static void Main() {
       
        int []a = { 1, 2, 3 };
   
         // size of the array
         int n = a.Length;
   
         // print and of all subarrays
         Console.WriteLine(AND(a, n));
    }
}

<?php
// PHP program to find of
// all the sub-arrays
 
// function to return AND
// of sub-arrays
function ANDS(&$a, $n)
{
    $ans = $a[0];
    for ($i = 0; $i < $n; ++$i)
        $ans &= $a[$i];
    return $ans;
}
 
// Driver Code
$a = array( 1, 2, 3 );
 
// size of the array
$n = sizeof($a);
 
// print and of all subarrays
echo ANDS($a, $n);
 
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
//Javascript program to find of all the sub-arrays
     
    //function to return AND of sub-arrays
    function AND(a,n)
    {
        let ans = a[0];
     for (let i = 0; i < n; ++i)
         ans &= a[i]; 
     return ans;
    }
     
    // Driver code
    let a=[ 1, 2, 3 ];
    // size of the array
    let n = a.length;
    // print and of all subarrays
    document.write(AND(a, n));
     
 
 
// This code is contributed by rag2127
</script>

PRODUCCIÓN: 

0

Complejidad de tiempo: O(N)