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>
Producción
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>
Producción
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