Compruebe si el AND bit a bit de un número con cualquier subconjunto de una array es cero o no

Dada una array y un Número N. La tarea es verificar si existe algún subconjunto de esta array tal que el AND bit a bit de este subconjunto con N sea cero.
Ejemplos : 
 

Input : arr[] = {1, 2, 4}  ;  N = 3
Output : YES
Explanation: The subsets are:
(1, 2 ), (1, 4), (1, 2, 4) 

Input : arr[] = {1, 1, 1}  ;  N = 3
Output : NO

Un enfoque simple es encontrar el AND bit a bit de todos los subconjuntos de la array y verificar si el AND de N con cualquier subconjunto es cero o no.
Un enfoque eficiente es observar que AND bit a bit de dos números cualesquiera siempre producirá un número menor o igual que el número más pequeño. Así que nuestra tarea es encontrar el subconjunto que tiene el valor mínimo de AND bit a bit. Entonces, como se indicó anteriormente, el AND de dos números cualesquiera siempre producirá un número menor o igual que el número mínimo, por lo que el valor mínimo de AND será el AND de todos los elementos de la array. Entonces, la tarea ahora se reduce a verificar el AND bit a bit de todos los elementos de la array y N, y si es cero, imprimiremos SÍ; de lo contrario, NO.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to check whether bitwise AND of a number
// with any subset of an array is zero or not
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether bitwise AND of a number
// with any subset of an array is zero or not
void isSubsetAndZero(int array[], int length, int N)
{
    // variable to store the
    // AND of all the elements
    int arrAnd = array[0];
 
    // find the AND of all the elements
    // of the array
    for (int i = 1; i < length; i++) {
        arrAnd = arrAnd & array[i];
    }
 
    // if the AND of all the array elements
    // and N is equal to zero
    if ((arrAnd & N) == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
// Driver Code
int main()
{
    int array[] = { 1, 2, 4 };
    int length = sizeof(array) / sizeof(int);
 
    int N = 3;
 
    isSubsetAndZero(array, length, N);
}

// Java program to check whether bitwise AND of a number
// with any subset of an array is zero or not
import java.io.*;
 
public class GFG {
 
 
// Function to check whether bitwise AND of a number
// with any subset of an array is zero or not
static void isSubsetAndZero(int array[], int length, int N)
{
    // variable to store the
    // AND of all the elements
    int arrAnd = array[0];
 
    // find the AND of all the elements
    // of the array
    for (int i = 1; i < length; i++) {
        arrAnd = arrAnd & array[i];
    }
 
    // if the AND of all the array elements
    // and N is equal to zero
    if ((arrAnd & N) == 0)
        System.out.println( "YES");
    else
        System.out.println( "NO");
}
 
// Driver Code
    public static void main (String[] args) {
        int array[] = { 1, 2, 4 };
    int length = array.length;
 
    int N = 3;
 
    isSubsetAndZero(array, length, N);
    }
}
//This code is contributed by shs..

# Python 3 program to check whether
# bitwise AND of a number with any
# subset of an array is zero or not
 
# Function to check whether bitwise
# AND of a number with any subset
# of an array is zero or not
def isSubsetAndZero(array, length, N):
 
    # variable to store the
    # AND of all the elements
    arrAnd = array[0]
 
    # find the AND of all
    # the elements of the array
    for i in range(1, length) :
        arrAnd = arrAnd & array[i]
 
    # if the AND of all the array
    # elements and N is equal to zero
    if ((arrAnd & N) == 0):
        print("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == "__main__":
    array = [ 1, 2, 4 ]
    length = len(array)
 
    N = 3
 
    isSubsetAndZero(array, length, N)
 
# This code is contributed
# by ChitraNayal

// C# program to check whether
// bitwise AND of a number with
// any subset of an array is zero or not
using System;
 
class GFG
{
 
// Function to check whether bitwise
// AND of a number with any subset
// of an array is zero or not
static void isSubsetAndZero(int []array,
                            int length, int N)
{
    // variable to store the
    // AND of all the elements
    int arrAnd = array[0];
 
    // find the AND of all the
    // elements of the array
    for (int i = 1; i < length; i++)
    {
        arrAnd = arrAnd & array[i];
    }
 
    // if the AND of all the array
    // elements and N is equal to zero
    if ((arrAnd & N) == 0)
        Console.WriteLine( "YES");
    else
        Console.WriteLine( "NO");
}
 
// Driver Code
public static void Main ()
{
    int []array = { 1, 2, 4 };
    int length = array.Length;
     
    int N = 3;
     
    isSubsetAndZero(array, length, N);
}
}
 
// This code is contributed
// by inder_verma

<?php
// PHP program to check whether
// bitwise AND of a number with
// any subset of an array is zero or not
 
// Function to check whether
// bitwise AND of a number with
// any subset of an array is zero or not
function isSubsetAndZero($array, $length, $N)
{
    // variable to store the
    // AND of all the elements
    $arrAnd = $array[0];
 
    // find the AND of all the
    // elements of the array
    for ($i = 1; $i <$length; $i++)
    {
        $arrAnd = $arrAnd & $array[$i];
    }
 
    // if the AND of all the array
    // elements and N is equal to zero
    if (($arrAnd & $N) == 0)
        echo("YES");
    else
        echo("NO");
}
 
// Driver Code
$array = array( 1, 2, 4 );
$length = count($array);
 
$N = 3;
 
isSubsetAndZero($array, $length, $N);
 
// This code is contributed
// by Shashank
?>

<script>
 
// Javascript implementation of the above approach
 
 
// Function to check whether bitwise AND of a number
// with any subset of an array is zero or not
function isSubsetAndZero(array, len, N)
{
    // variable to store the
    // AND of all the elements
    var arrAnd = array[0];
 
    // find the AND of all the elements
    // of the array
    for (var i = 1; i < len; i++) {
        arrAnd = arrAnd & array[i];
    }
 
    // if the AND of all the array elements
    // and N is equal to zero
    if ((arrAnd & N) == 0)
        document.write("YES"+"<br>");
    else
        document.write("NO"+"<br>");
}
 
 
 
var array = [1, 2, 4 ];
var len = array.length;
var N = 3;
isSubsetAndZero(array, len, N);
 
// This code is contributed by SoumikMondal
 
</script>

YES