Tamaño del subconjunto más pequeño con máximo Bitwise OR

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: 

  1. Generamos todos los subconjuntos y devolvemos el tamaño más pequeño con OR dado
  2. 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

Deja una respuesta

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