Subsecuencia más larga con un valor AND dado | EN)

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

Entrada: arr[] = {3, 7, 2, 3}, M = 3 
Salida: 3 
{3, 7, 3} es la subsecuencia requerida. 
3 & 7 & 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 AND requerido.
Enfoque eficiente: una observación clave es que todos los números en la subsecuencia requerida deben generar el valor M cuando se les aplica AND con M . Así que filtre todos los elementos cuyo AND 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 combinarán con AND. Si el resultado de este AND 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 AND solo desarma los bits 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 AND of all the
    // filtered elements
    int c_and = filter[0];
    for (int i = 1; i < filter.size(); i++)
        c_and &= filter[i];
 
    // Check if the AND is equal to m
    if (c_and == 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<>();
 
    // 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 AND of all the
    // filtered elements
    int c_and = filter.get(0);
    for (int i = 1; i < filter.size(); i++)
        c_and &= filter.get(i);
 
    // Check if the AND is equal to m
    if (c_and == 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.println(findLen(arr, n, m));
}
}
 
// This code is contributed by PrinciRaj1992

# 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_and = filter[0];
    for i in range(1, len(filter)) :
        c_and &= filter[i];
 
    # Check if the OR is equal to m
    if (c_and == 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 AND of all the
    // filtered elements
    int c_and = filter[0];
    for (int i = 1; i < filter.Count; i++)
        c_and &= filter[i];
 
    // Check if the AND is equal to m
    if (c_and == m)
        return filter.Count;
 
    return 0;
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 7, 3, 3, 1, 3 };
    int n = arr.Length;
    int m = 3;
 
    Console.WriteLine(findLen(arr, n, m));
}
}
 
// This code is contributed by 29AjayKumar

<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 AND of all the
    // filtered elements
    var c_and = filter[0];
    for (var i = 1; i < filter.length; i++)
        c_and &= filter[i];
 
    // Check if the AND is equal to m
    if (c_and == 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)