Subsecuencia más larga con un valor OR dado: Enfoque O(N)

Dada una array arr[] , la tarea es encontrar la subsecuencia más larga con un valor OR dado M . Si no existe tal subsecuencia, imprima 0 . 
Ejemplos: 
 

Entrada: arr[] = {3, 7, 2, 3}, M = 3 
Salida: 3 
{3, 2, 3} es la subsecuencia requerida 
3 | 2 | 3 = 3
Entrada: arr[] = {2, 2}, M = 3 
Salida: 0 
 

Enfoque ingenuo: una forma simple de resolver este problema es generar todas las subsecuencias posibles y luego encontrar la más grande entre ellas con el valor OR requerido.
Enfoque eficiente: una observación clave es que todos los números en la subsecuencia requerida deben generar el valor M cuando se combinan con M . Así que filtre todos los elementos cuyo OR con M sea igual a M . 
Ahora, la tarea es encontrar la subsecuencia más larga entre este subconjunto filtrado. Es bastante obvio que todos estos números se unirán con OR. Si el resultado de este OR es M , la respuesta será igual al tamaño de este conjunto filtrado. De lo contrario la respuesta será 0. Esto se debe a que OR solo establece los bits no establecidos. Entonces, cuanto más grandes son los números en el conjunto, más óptimo es.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the required length
int findLen(int* arr, int n, int m)
{
    // To store the filtered numbers
    vector<int> filter;
 
    // Filtering the numbers
    for (int i = 0; i < n; i++)
        if ((arr[i] | m) == m)
            filter.push_back(arr[i]);
 
    // If there are no elements to check
    if (filter.size() == 0)
        return 0;
 
    // Find the OR of all the
    // filtered elements
    int c_or = filter[0];
    for (int i = 1; i < filter.size(); i++)
        c_or |= filter[i];
 
    // Check if the OR is equal to m
    if (c_or == m)
        return filter.size();
 
    return 0;
}
 
// Driver code
int main()
{
    int arr[] = { 7, 3, 3, 1, 3 };
    int n = sizeof(arr) / sizeof(int);
    int m = 3;
 
    cout << findLen(arr, n, m);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the required length
static int findLen(int arr[], int n, int m)
{
    // To store the filtered numbers
    Vector<Integer> filter = new Vector<Integer>();
 
    // Filtering the numbers
    for (int i = 0; i < n; i++)
        if ((arr[i] | m) == m)
            filter.add(arr[i]);
 
    // If there are no elements to check
    if (filter.size() == 0)
        return 0;
 
    // Find the OR of all the
    // filtered elements
    int c_or = filter.get(0);
    for (int i = 1; i < filter.size(); i++)
        c_or |= filter.get(i);
 
    // Check if the OR is equal to m
    if (c_or == m)
        return filter.size();
 
    return 0;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 7, 3, 3, 1, 3 };
    int n = arr.length;
    int m = 3;
 
    System.out.print(findLen(arr, n, m));
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
# Function to return the required length
def findLen(arr, n, m) :
 
    # To store the filtered numbers
    filter = [];
 
    # Filtering the numbers
    for i in range(n) :
        if ((arr[i] | m) == m) :
            filter.append(arr[i]);
 
    # If there are no elements to check
    if (len(filter) == 0) :
        return 0;
 
    # Find the OR of all the
    # filtered elements
    c_or = filter[0];
    for i in range(1, len(filter)) :
        c_or |= filter[i];
 
    # Check if the OR is equal to m
    if (c_or == m) :
        return len(filter);
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 7, 3, 3, 1, 3 ];
    n = len(arr);
    m = 3;
 
    print(findLen(arr, n, m));
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
using System.Collections.Generic;
 
class GFG
{
 
// Function to return the required length
static int findLen(int [] arr, int n, int m)
{
    // To store the filtered numbers
    List<int> filter = new List<int>();
 
    // Filtering the numbers
    for (int i = 0; i < n; i++)
        if ((arr[i] | m) == m)
            filter.Add(arr[i]);
 
    // If there are no elements to check
    if (filter.Count == 0)
        return 0;
 
    // Find the OR of all the
    // filtered elements
    int c_or = filter[0];
    for (int i = 1; i < filter.Count; i++)
        c_or |= filter[i];
 
    // Check if the OR is equal to m
    if (c_or == m)
        return filter.Count;
 
    return 0;
}
 
// Driver code
public static void Main()
{
    int []arr = { 7, 3, 3, 1, 3 };
    int n = arr.Length;
    int m = 3;
 
    Console.Write(findLen(arr, n, m));
}
}
 
// This code is contributed by Mohit kumar 29

<script>
 
// Javascript implementation of the approach
 
// Function to return the required length
function findLen(arr, n, m)
{
    // To store the filtered numbers
    var filter = [];
 
    // Filtering the numbers
    for (var i = 0; i < n; i++)
        if ((arr[i] | m) == m)
            filter.push(arr[i]);
 
    // If there are no elements to check
    if (filter.length == 0)
        return 0;
 
    // Find the OR of all the
    // filtered elements
    var c_or = filter[0];
    for (var i = 1; i < filter.length; i++)
        c_or |= filter[i];
 
    // Check if the OR is equal to m
    if (c_or == m)
        return filter.length;
 
    return 0;
}
 
// Driver code
var arr = [7, 3, 3, 1, 3 ];
var n = arr.length;
var m = 3;
document.write( findLen(arr, n, m));
 
</script>

4

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)