Dada una array de enteros positivos. La tarea es encontrar el tamaño del subconjunto más pequeño tal que el Bitwise OR de ese conjunto sea el Máximo posible.
Ejemplos :
Input : arr[] = {5, 1, 3, 4, 2} Output : 2 7 is the maximum value possible of OR, 5|2 = 7 and 5|3 = 7 Input : arr[] = {2, 6, 2, 8, 4, 5} Output : 3 15 is the maximum value of OR and set elements are 8, 6, 5
Fuente : Pasantía de Sprinklr en Campus
Hacer OR bit a bit de un número con algún valor no disminuye su valor. O mantiene el mismo valor o aumenta. Si observamos más de cerca el problema, podemos notar que el valor OR máximo que podemos obtener es haciendo OR bit a bit de todos los elementos de la array. Pero esto incluye todos los elementos y aquí quiero saber el subconjunto más pequeño. Así que hacemos lo siguiente.
I) Encuentre OR bit a bit de todos los elementos de la array. Este es el quirófano que estamos buscando.
II) Ahora necesitamos encontrar el subconjunto más pequeño con este OR bit a bit. Este problema es similar al problema de la suma de subconjuntos, podemos resolverlo de dos maneras:
- Generamos todos los subconjuntos y devolvemos el tamaño más pequeño con OR dado
- Usamos Programación Dinámica para resolver el problema. Esta solución va a ser muy similar al subconjunto de tamaño máximo con suma dada
La complejidad temporal de la primera solución es O(2 n ) y la complejidad temporal de la solución de programación dinámica es O(OR * n) donde OR es OR de todos los elementos de la array y n es el tamaño de la array de entrada.
Usando el Método 1: (generar todos los subconjuntos y devolver el tamaño más pequeño con OR dado)
C++
// CPP Code for above approach #include <bits/stdc++.h> using namespace std; // Compute bitwise or of all elements // in array of size sz int OR(int data[], int sz) { int mOR = 0; for (int i = 0; i < sz; ++i) { mOR |= data[i]; } return mOR; } // calculate the size of // minimum subset with maximum or int minSubset(int data[], int sz,int maxOR) { // store the minimum size of // the subset with maximum OR int minSZ=sz; // generates all subsets for(int mask=0;mask<(1<<sz);mask++) { // stores the size of the current subset int curSZ=0; // stores the OR of all the elements // in the current subset int curOR=0; for(int i=0;i<sz;i++) { if(mask&(1<<i)) { curSZ++; curOR|=data[i]; } } if(curOR==maxOR) minSZ=min(minSZ,curSZ); } return minSZ; } // Driver code int main() { int data[] = { 5, 1, 3, 4, 2 }; int sz = sizeof(data) / sizeof(0); int maxOR = OR(data, sz); // Function Call cout << minSubset(data, sz,maxOR) << '\n' ; }
Java
// Java Program for above approach import java.io.*; import java.util.*; class Solution { // Compute bitwise or of all elements // in array of size sz private static int OR(int[] arr) { int mOR = 0; for (int i = 0; i < arr.length; ++i) { mOR |= arr[i]; } return mOR; } // Recursively calculating the size of // minimum subset with maximum or private static int maxSubset(int[] arr, int i, int curOr, int curSize, int maxOr) { // If i is arr.length if (i == arr.length) { // If curOr is equal to maxOr if (curOr == maxOr) { return curSize; } // Return arr.length else { return arr.length; } } // Try the current element in the subset int take = maxSubset(arr, i + 1, curOr | arr[i], curSize + 1, maxOr); // Skip the current element int notTake = maxSubset(arr, i + 1, curOr, curSize, maxOr); // Return minimum of take and notTake return Math.min(take, notTake); } // Driver Code public static void main(String[] args) { int[] data = {5, 1, 3, 4, 2}; int maxOr = OR(data); // Function Call int maxSubsetSize = maxSubset(data, 0, 0, 0, maxOr); System.out.println(maxSubsetSize); } } // Code contributed by Abdelaziz EROUI
Python3
# Python3 Code for above approach # Compute bitwise or of all elements # in array of size sz def OR(data, sz): mOR = 0 for i in range(sz) : mOR |= data[i] return mOR # calculate the size of # minimum subset with maximum or def minSubset(data, sz,maxOR): # store the minimum size of # the subset with maximum OR minSZ=sz # generates all subsets for mask in range(1<<sz): # stores the size of the current subset curSZ=0 # stores the OR of all the elements # in the current subset curOR=0 for i in range(sz): if(mask&(1<<i)): curSZ+=1 curOR|=data[i] if(curOR==maxOR): minSZ=min(minSZ,curSZ) return minSZ # Driver code if __name__ == '__main__': data =[5, 1, 3, 4, 2] sz = len(data) maxOR = OR(data, sz) # Function Call print(minSubset(data, sz,maxOR))
C#
// C# Program for above approach using System; class Solution { // Compute bitwise or of all elements // in array of size sz private static int OR(int[] arr) { int mOR = 0; for (int i = 0; i < arr.Length; ++i) { mOR |= arr[i]; } return mOR; } // Recursively calculating the size of // minimum subset with maximum or private static int maxSubset(int[] arr, int i, int curOr, int curSize, int maxOr) { // If i is arr.length if (i == arr.Length) { // If curOr is equal to maxOr if (curOr == maxOr) { return curSize; } // Return arr.length else { return arr.Length; } } // Try the current element in the subset int take = maxSubset(arr, i + 1, curOr | arr[i], curSize + 1, maxOr); // Skip the current element int notTake = maxSubset(arr, i + 1, curOr, curSize, maxOr); // Return minimum of take and notTake return Math.Min(take, notTake); } // Driver Code static void Main() { int[] data = {5, 1, 3, 4, 2}; int maxOr = OR(data); // Function Call int maxSubsetSize = maxSubset(data, 0, 0, 0, maxOr); Console.WriteLine(maxSubsetSize); } } // This code is contributed by SoumikMondal
Javascript
<script> // JavaScript Program for above approach // Compute bitwise or of all elements // in array of size sz function OR(arr) { let mOR = 0; for (let i = 0; i < arr.length; ++i) { mOR |= arr[i]; } return mOR; } // Recursively calculating the size of // minimum subset with maximum or function maxSubset(arr,i,curOr,curSize,maxOr) { // If i is arr.length if (i == arr.length) { // If curOr is equal to maxOr if (curOr == maxOr) { return curSize; } // Return arr.length else { return arr.length; } } // Try the current element in the subset let take = maxSubset(arr, i + 1, curOr | arr[i], curSize + 1, maxOr); // Skip the current element let notTake = maxSubset(arr, i + 1, curOr, curSize, maxOr); // Return minimum of take and notTake return Math.min(take, notTake); } // Driver Code let data=[5, 1, 3, 4, 2]; let maxOr = OR(data); // Function Call let maxSubsetSize = maxSubset(data, 0, 0, 0, maxOr); document.write(maxSubsetSize); // This code is contributed by rag2127 </script>
2
Complejidad temporal: O(2 n )
Espacio auxiliar: O(n)
Usando el Método 2:
Primero encontramos el OR de todos los elementos de la array dada. Ahora necesitamos encontrar el subconjunto más pequeño con este OR bit a bit.
Para hacerlo, use el enfoque DP similar al que se proporciona en el problema de suma de subconjuntos . count[i][j] denota el subconjunto de tamaño mínimo hasta el i-ésimo elemento cuyo OR es j.
C++
// CPP Code for above approach #include <bits/stdc++.h> using namespace std; // Compute bitwise or of all elements // in array of size sz int OR(int data[], int sz) { int mOR = 0; for (int i = 0; i < sz; ++i) { mOR |= data[i]; } return mOR; } // calculate the size of // minimum subset with maximum or int minSubset(int data[], int sz, int maxOR) { // count table where // count[i][j] => minimum size subset till ith element // whose OR is j vector<vector<int> > count(sz + 1, vector<int>(maxOR + 1, 1e9)); count[0][0] = 0; for (int i = 0; i < sz; i++) { for (int j = 0; j <= maxOR; j++) { // Do not consider ith element. count[i + 1][j] = min(count[i + 1][j], count[i][j]); // Consider the ith element. if (count[i][j] != 1e9) { count[i + 1][j | data[i]] = min( count[i + 1][j | data[i]], count[i][j] + 1); } } } return count[sz][maxOR]; } // Driver code int main() { int data[] = { 5, 1, 3, 4, 2 }; int sz = sizeof(data) / sizeof(0); int maxOR = OR(data, sz); // Function Call cout << minSubset(data, sz, maxOR) << '\n'; }
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { // Java Code for above approach // Compute bitwise or of all elements // in array of size sz static int OR(int data[], int sz) { int mOR = 0; for (int i = 0; i < sz; ++i) { mOR |= data[i]; } return mOR; } // calculate the size of // minimum subset with maximum or static int minSubset(int data[], int sz, int maxOR) { // count table where // count[i][j] => minimum size subset till ith element // whose OR is j int count[][] = new int[sz + 1][maxOR + 1]; for(int i=0;i<sz+1;i++){ Arrays.fill(count[i],1000000000); } count[0][0] = 0; for (int i = 0; i < sz; i++) { for (int j = 0; j <= maxOR; j++) { // Do not consider ith element. count[i + 1][j] = Math.min(count[i + 1][j], count[i][j]); // Consider the ith element. if (count[i][j] != 1000000000) { count[i + 1][j | data[i]] = Math.min( count[i + 1][j | data[i]], count[i][j] + 1); } } } return count[sz][maxOR]; } /* Driver program to test above function*/ public static void main(String args[]) { int data[] = { 5, 1, 3, 4, 2 }; int sz = data.length; int maxOR = OR(data, sz); // Function Call System.out.println(minSubset(data, sz, maxOR)); } } // This code is contributed by shinjanpatra.
Python3
# Python3 Code for above approach # Compute bitwise or of all elements # in array of size sz def OR(data, sz): mOR = 0 for i in range(sz): mOR |= data[i] return mOR # calculate the size of # minimum subset with maximum or def minSubset(data, sz, maxOR): # count table where # count[i][j] => minimum size subset till ith element # whose OR is j count=[[1e9 for _ in range(maxOR+1)]for _ in range(sz+1)] count[0][0] = 0 for i in range(sz) : for j in range(maxOR) : # Do not consider ith element. count[i + 1][j] = min(count[i + 1][j], count[i][j]) # Consider the ith element. if (count[i][j] != 1e9) : count[i + 1][j | data[i]] = min( count[i + 1][j | data[i]], count[i][j] + 1) return count[sz][maxOR] # Driver code if __name__ == '__main__': data = [5, 1, 3, 4, 2] sz = len(data) maxOR = OR(data, sz) # Function Call print(minSubset(data, sz, maxOR))
Javascript
<script> // JavaScript Code for above approach // Compute bitwise or of all elements // in array of size sz function OR(data, sz){ let mOR = 0 for(let i=0;i<sz;i++) mOR |= data[i] return mOR } // calculate the size of // minimum subset with maximum or function minSubset(data, sz, maxOR){ // count table where // count[i][j] => minimum size subset till ith element // whose OR is j let count = new Array(sz+1).fill(0).map(()=>new Array(maxOR+1).fill(1e9)); count[0][0] = 0 for(let i=0;i<sz;i++){ for(let j=0;j<maxOR;j++){ // Do not consider ith element. count[i + 1][j] = Math.min(count[i + 1][j], count[i][j]) // Consider the ith element. if (count[i][j] != 1e9) count[i + 1][j | data[i]] = Math.min( count[i + 1][j | data[i]], count[i][j] + 1) } } return count[sz][maxOR] } // Driver code let data = [5, 1, 3, 4, 2] let sz = data.length let maxOR = OR(data, sz) // Function Call document.write(minSubset(data, sz, maxOR),"</br>") // This code is contributed by shinjanpatra </script>
2
Complejidad temporal: O(n*maxOR) donde n es el tamaño del arreglo y maxOR es el máximo o que se puede obtener.
Espacio Auxiliar: O(n*maxOR)
Publicación traducida automáticamente
Artículo escrito por Kushdeep_Mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA