Longitud de la subsecuencia más larga cuyo valor XOR es impar

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros positivos, la tarea es encontrar la longitud de la subsecuencia más larga tal que Bitwise XOR de todos los enteros en la subsecuencia sea impar.

Ejemplos:

Entrada: N = 7, arr[] ={2, 3, 4, 1, 5, 6, 7}
Salida: 6
Explicación: La subsecuencia de longitud máxima es {2 , 3, 4, 5, 6, 7 } 
con XOR de todos los elementos como 1.
También existen otras subsecuencias.

Entrada: N = 4, arr[] = {2, 4, 6, 8}
Salida: 0
Explicación: No hay salidas de subsecuencia posibles.

 

Enfoque ingenuo: la idea ingenua es generar todas las subsecuencias posibles de la array dada y verificar si Bitwise XOR de cualquier subsecuencia es impar o no. Si existen subsecuencias cuyo Bitwise XOR es impar, imprima la longitud máxima de esa entre esas subsecuencias.

Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque ingenuo anterior, la idea es contar la cantidad de elementos pares e impares en la array dada y encontrar la longitud de la subsecuencia más larga como se muestra a continuación:

  1. Cuenta el número de elementos pares e impares en arr[] .
  2. Si el recuento de valores impares es igual al tamaño de la array, es decir, N , entonces tenemos dos casos posibles:
    1. Si el tamaño de la array es impar, la longitud máxima será igual a N
    2. De lo contrario, la longitud máxima será igual a N – 1 .
  3. Si el recuento de valores pares es igual al tamaño de la array, la longitud máxima será cero.
  4. Ahora, si ambos tipos de elementos están presentes en la array dada, entonces la longitud máxima incluirá todos los elementos pares y para los elementos impares, los incluimos todos si el recuento de valores impares es impar; de lo contrario, incluimos elementos impares: 1 .
  5. Imprime la longitud máxima de la subsecuencia más larga después de los pasos anteriores.

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

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function for find max XOR subsequence
// having odd value
int maxXORSubsequence(int arr[], int n)
{
 
    // Initialize odd and even count
    int odd = 0, even = 0;
 
    // Count the number of odd and even
    // numbers in given array
    for (int i = 0; i < n; i++) {
        if (arr[i] & 1)
            odd++;
        else
            even++;
    }
 
    int maxlen;
 
    if (odd == n) {
 
        // if all values are odd
        // in given array
        if (odd % 2 == 0)
            maxlen = n - 1;
        else
            maxlen = n;
    }
    else if (even == n) {
 
        // if all values are even
        // in given array
        maxlen = 0;
    }
    else {
 
        // if both odd and even are
        // present in given array
        if (odd % 2 == 0)
            maxlen = even + odd - 1;
        else
            maxlen = even + odd;
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 2, 3, 4, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << maxXORSubsequence(arr, n);
}

Java

// Java program for the above approach
class GFG{
     
// Function for find max XOR subsequence
// having odd value
static int maxXORSubsequence(int arr[], int n)
{
     
    // Initialize odd and even count
    int i, odd = 0, even = 0;
 
    // Count the number of odd and even
    // numbers in given array
    for(i = 0; i < n; i++)
    {
        if ((arr[i] & 1) != 0)
            odd++;
        else
            even++;
    }
 
    int maxlen;
 
    if (odd == n)
    {
         
        // If all values are odd
        // in given array
        if (odd % 2 == 0)
            maxlen = n - 1;
        else
            maxlen = n;
    }
    else if (even == n)
    {
 
        // If all values are even
        // in given array
        maxlen = 0;
    }
    else
    {
 
        // If both odd and even are
        // present in given array
        if (odd % 2 == 0)
            maxlen = even + odd - 1;
        else
            maxlen = even + odd;
    }
    return maxlen;
}
 
// Driver Code
public static void main (String []args)
{
     
    // Given array arr[]
    int arr[] = { 2, 3, 4, 5, 6, 7 };
    int n = arr.length;
 
    // Function Call
    System.out.print( maxXORSubsequence(arr, n));
}
}
 
// This code is contributed by chitranayal

Python3

# Python3 program for the above approach
 
# Function for find max XOR subsequence
# having odd value
def maxXorSubsequence(arr, n):
     
    # Initialize odd and even count
    odd = 0
    even = 0
     
    # Count the number of odd and even
    # numbers in given array
    for i in range(0, n):
        if arr[i] % 2 != 0:
            odd += 1
        else:
            even += 1
    if odd == n:
         
        # If all values are odd
        # in given array
        if odd % 2 == 0:
            maxlen = n - 1
        else:
            maxlen = n
             
    elif even == n:
         
        # If all values are even
        # in given array
        maxlen = 0
    else:
         
        # If both odd and even are
        # present in given array
        if odd % 2 == 0:
            maxlen = even + odd - 1
        else:
            maxlen = even + odd
             
    return maxlen
 
# Driver code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 2, 3, 4, 5, 6, 7 ]
    n = len(arr)
     
    # Function Call
    print(maxXorSubsequence(arr,n))
     
# This code is contributed by virusbuddah_

C#

// C# program for the above approach
using System;
class GFG{
      
// Function for find max XOR subsequence
// having odd value
static int maxXORSubsequence(int[] arr, int n)
{
      
    // Initialize odd and even count
    int i, odd = 0, even = 0;
  
    // Count the number of odd and even
    // numbers in given array
    for(i = 0; i < n; i++)
    {
        if ((arr[i] & 1) != 0)
            odd++;
        else
            even++;
    }
  
    int maxlen;
  
    if (odd == n)
    {
          
        // If all values are odd
        // in given array
        if (odd % 2 == 0)
            maxlen = n - 1;
        else
            maxlen = n;
    }
    else if (even == n)
    {
  
        // If all values are even
        // in given array
        maxlen = 0;
    }
    else
    {
  
        // If both odd and even are
        // present in given array
        if (odd % 2 == 0)
            maxlen = even + odd - 1;
        else
            maxlen = even + odd;
    }
    return maxlen;
}
  
// Driver Code
public static void Main (string []args)
{
      
    // Given array arr[]
    int []arr = { 2, 3, 4, 5, 6, 7 };
    int n = arr.Length;
  
    // Function Call
    Console.Write( maxXORSubsequence(arr, n));
}
}
  
// This code is contributed by rock_cool

Javascript

<script>
 
// Javascript program for the above approach
 
// Function for find max XOR subsequence
// having odd value
function maxXORSubsequence(arr, n)
{
     
    // Initialize odd and even count
    let odd = 0, even = 0;
 
    // Count the number of odd and even
    // numbers in given array
    for(let i = 0; i < n; i++)
    {
        if ((arr[i] & 1) != 0)
            odd++;
        else
            even++;
    }
 
    let maxlen;
 
    if (odd == n)
    {
         
        // If all values are odd
        // in given array
        if (odd % 2 == 0)
            maxlen = n - 1;
        else
            maxlen = n;
    }
    else if (even == n)
    {
         
        // If all values are even
        // in given array
        maxlen = 0;
    }
    else
    {
         
        // If both odd and even are
        // present in given array
        if (odd % 2 == 0)
            maxlen = even + odd - 1;
        else
            maxlen = even + odd;
    }
    return maxlen;
}
 
// Driver code
 
// Given array arr[]
let arr = [ 2, 3, 4, 5, 6, 7 ];
let n = arr.length;
 
// Function Call
document.write(maxXORSubsequence(arr, n));
 
// This code is contributed by divyesh072019
     
</script>
Producción:

6

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por pegasus12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *