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++
// 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
// 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.
Python3
# 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#
// 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.
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA