Encuentre el tamaño del subconjunto más grande con AND bit a bit mayor que su XOR bit a bit

Dada una array arr[] de N enteros, la tarea es encontrar el tamaño del subconjunto más grande de modo que el AND bit a bit de todos los elementos del subconjunto sea mayor que el XOR bit a bit de todos los elementos del subconjunto.

Ejemplo:

Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 2
Explicación: El subconjunto {2, 3} tiene el AND bit a bit de todos los elementos como 2 mientras que el XOR bit a bit de todos los elementos es 1. Por lo tanto, AND bit a bit > XOR bit a bit. Por lo tanto, el tamaño requerido del subconjunto es 2, que es el máximo posible. Otro ejemplo de un subconjunto válido es {4, 5}.

Entrada: arr[] = {24, 20, 18, 17, 16}
Salida: 4

Enfoque: el problema dado se puede resolver generando todos los subconjuntos posibles del conjunto dado utilizando un enfoque recursivo y manteniendo el valor de AND bit a bit y XOR bit a bit de todos y cada uno de los subconjuntos. La respuesta requerida será el tamaño máximo del subconjunto tal que sea bit a bit Y > sea bit a bit XOR.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to iterate over all
// the subsets of the given array and return
// the maximum size of subset such that the
// bitwise AND > bitwise OR of all elements
int maxSizeSubset(
    int* arr, int N, int bitwiseXOR,
    int bitwiseAND, int i, int len = 0)
{
    // Stores the maximum length of subset
    int ans = INT_MIN;
 
    // Update ans
    if (bitwiseAND > bitwiseXOR) {
        ans = len;
    }
 
    // Base Case
    if (i == N) {
        return ans;
    }
 
    // Recursive call excluding the
    // ith element of the given array
    ans = max(ans, maxSizeSubset(
                       arr, N, bitwiseXOR,
                       bitwiseAND, i + 1, len));
 
    // Recursive call including the ith element
    // of the given array
    ans = max(ans,
              maxSizeSubset(
                  arr, N,
                  (arr[i] ^ bitwiseXOR),
                  (arr[i] & bitwiseAND), i + 1,
                  len + 1));
 
    // Return Answer
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 24, 20, 18, 17, 16 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxSizeSubset(
        arr, N, 0,
        pow(2, 10) - 1, 0);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG {
 
// Recursive function to iterate over all
// the subsets of the given array and return
// the maximum size of subset such that the
// bitwise AND > bitwise OR of all elements
static int maxSizeSubset(
    int[] arr, int N, int bitwiseXOR,
    int bitwiseAND, int i, int len)
{
   
    // Stores the maximum length of subset
    int ans = Integer.MIN_VALUE;
 
    // Update ans
    if (bitwiseAND > bitwiseXOR) {
        ans = len;
    }
 
    // Base Case
    if (i == N) {
        return ans;
    }
 
    // Recursive call excluding the
    // ith element of the given array
    ans = Math.max(ans, maxSizeSubset(
                       arr, N, bitwiseXOR,
                       bitwiseAND, i + 1, len));
 
    // Recursive call including the ith element
    // of the given array
    ans = Math.max(ans,
              maxSizeSubset(
                  arr, N,
                  (arr[i] ^ bitwiseXOR),
                  (arr[i] & bitwiseAND), i + 1,
                  len + 1));
 
    // Return Answer
    return ans;
}
 
// Driver Code
public static void main (String[] args) {
         
    int arr[] = { 24, 20, 18, 17, 16 };
    int N = arr.length;
 
    System.out.println(maxSizeSubset(arr, N, 0, (int)Math.pow(2, 10) - 1, 0, 0));
}
}
 
// This code is contributed by target_2.

# Python Program to implement
# the above approach
import sys
 
# Recursive function to iterate over all
# the subsets of the given array and return
# the maximum size of subset such that the
# bitwise AND > bitwise OR of all elements
def maxSizeSubset(arr, N, bitwiseXOR,
                    bitwiseAND, i, len) :
                         
    # Stores the maximum length of subset
    ans = -sys.maxsize - 1
 
    # Update ans
    if (bitwiseAND > bitwiseXOR) :
        ans = len
     
 
    # Base Case
    if (i == N) :
        return ans
     
 
    # Recursive call excluding the
    # ith element of the given array
    ans = max(ans, maxSizeSubset(
                       arr, N, bitwiseXOR,
                       bitwiseAND, i + 1, len))
 
    # Recursive call including the ith element
    # of the given array
    ans = max(ans,
              maxSizeSubset(
                  arr, N,
                  (arr[i] ^ bitwiseXOR),
                  (arr[i] & bitwiseAND), i + 1,
                  len + 1))
 
    # Return Answer
    return ans
 
 
# Driver Code
 
arr = [ 24, 20, 18, 17, 16 ]
N = len(arr)
 
print(maxSizeSubset(arr, N, 0,
            pow(2, 10) - 1, 0, 0))
 
# This code is contributed by sanjoy_62.

// C# program for the above approach
using System;
class GFG {
 
// Recursive function to iterate over all
// the subsets of the given array and return
// the maximum size of subset such that the
// bitwise AND > bitwise OR of all elements
static int maxSizeSubset(
    int []arr, int N, int bitwiseXOR,
    int bitwiseAND, int i, int len)
{
   
    // Stores the maximum length of subset
    int ans = Int32.MinValue;
 
    // Update ans
    if (bitwiseAND > bitwiseXOR) {
        ans = len;
    }
 
    // Base Case
    if (i == N) {
        return ans;
    }
 
    // Recursive call excluding the
    // ith element of the given array
    ans = Math.Max(ans, maxSizeSubset(
                       arr, N, bitwiseXOR,
                       bitwiseAND, i + 1, len));
 
    // Recursive call including the ith element
    // of the given array
    ans = Math.Max(ans,
              maxSizeSubset(
                  arr, N,
                  (arr[i] ^ bitwiseXOR),
                  (arr[i] & bitwiseAND), i + 1,
                  len + 1));
 
    // Return Answer
    return ans;
}
 
// Driver Code
public static void Main () {
         
    int []arr = { 24, 20, 18, 17, 16 };
    int N = arr.Length;
 
    Console.Write(maxSizeSubset(arr, N, 0, (int)Math.Pow(2, 10) - 1, 0, 0));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
       // JavaScript Program to implement
       // the above approach
 
       // Recursive function to iterate over all
       // the subsets of the given array and return
       // the maximum size of subset such that the
       // bitwise AND > bitwise OR of all elements
       function maxSizeSubset(
           arr, N, bitwiseXOR,
           bitwiseAND, i, len = 0)
      {
           // Stores the maximum length of subset
           let ans = Number.MIN_VALUE;
 
           // Update ans
           if (bitwiseAND > bitwiseXOR) {
               ans = len;
           }
 
           // Base Case
           if (i == N) {
               return ans;
           }
 
           // Recursive call excluding the
           // ith element of the given array
           ans = Math.max(ans, maxSizeSubset(
               arr, N, bitwiseXOR,
               bitwiseAND, i + 1, len));
 
           // Recursive call including the ith element
           // of the given array
           ans = Math.max(ans,
               maxSizeSubset(
                   arr, N,
                   (arr[i] ^ bitwiseXOR),
                   (arr[i] & bitwiseAND), i + 1,
                   len + 1));
 
           // Return Answer
           return ans;
       }
 
       // Driver Code
       let arr = [24, 20, 18, 17, 16];
       let N = arr.length;
 
       document.write(maxSizeSubset(
           arr, N, 0,
           Math.pow(2, 10) - 1, 0))
 
   // This code is contributed by Potta Lokesh
   </script>

4

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