Encuentre el valor Y máximo entre todos los subconjuntos de tamaño K de una array dada

Dada una array arr[] que contiene N enteros no negativos, la tarea es encontrar el valor AND máximo entre todos los subconjuntos que tienen una longitud K

Ejemplos: 

Entrada: arr[] = {1, 6, 9, 7}, K = 1
Salida: 9
Explicación: Como solo se permite un elemento, 9 es el mayor valor que se puede obtener.

Entrada: arr[] = {3, 3, 3}, K = 2
Salida: 3

Entrada: arr[] = {7, 8, 9, 10, 11, 12}, K = 3
Salida: 8

 

Enfoque ingenuo: el enfoque más simple es generar todos los subconjuntos posibles de longitud K y encontrar el subconjunto de valor AND máximo entre ellos.

Complejidad temporal: O(2 N . N)
Espacio auxiliar: O(N)

Solución eficiente: la contribución de un bit en cualquier posición es mayor que la contribución combinada de todos los bits a su derecha. Esto significa que el significado de los bits importa de izquierda a derecha (MSB a LSB). Por lo tanto, intente con avidez establecer primero los bits más a la izquierda y verifique los números que lo ayudarán a hacerlo. Siga los pasos a continuación para encontrar el subconjunto de longitud K que tiene el valor AND máximo:

  1. Considere inicializar este conjunto óptimo con todos los valores en la array.
  2. Iterar sobre todas las posiciones de los bits desde i = 30 hasta 0.
  3. Compruebe si hay más de K números que tienen su bit establecido en la i-ésima posición
  4. Si lo hay, actualice el conjunto óptimo con este nuevo conjunto de valores (que no es más que un subconjunto del conjunto óptimo)
  5. Si en cualquier iteración el tamaño del subconjunto se convierte exactamente en K , rompa y devuelva ese conjunto.

Nota: También es posible que haya más de K valores en nuestro conjunto después de todas las iteraciones. Esto simplemente significará que hay algunos números repetidos en el conjunto (por lo que no afectarán la respuesta). 
Aquí hay un ejemplo que se puede considerar:
arr[] = {3, 3, 3}, K = 2
ans = 3 & 3 = 3 (si este conjunto óptimo se imprime usando el siguiente código, la respuesta será [3, 3 , 3] que no afectará al máximo y del subconjunto)

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum AND
// value of all the subsets having length K
int maxAndSubset(int arr[], int N, int K)
{
    // Initializing the optimal_set
    vector<int> optimal_set(arr, arr + N);
 
    // Iterating for every position of bits
    for (int j = 30; j >= 0; j--) {
        vector<int> new_optimal_set;
 
        // Checking if the bits at jth
        // position can be obtained set
        // among the numbers available
        // from optimal_set set
        for (auto element : optimal_set) {
            if ((1 << j) & element) {
 
                // If bit set at position j,
                // add into new_optimal_set
                new_optimal_set.push_back(element);
            }
        }
        if (new_optimal_set.size() < K)
            continue;
 
        // Updating optimal_set with new_optimal_set
        optimal_set = new_optimal_set;
        if (optimal_set.size() == K)
            break;
    }
 
    int ans = (1 << 30) - 1;
 
    for (auto element : optimal_set) {
        ans &= element;
    }
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 7, 8, 9, 10, 11, 12 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    cout << maxAndSubset(arr, N, K);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class GFG
{
 
  // Function to find the maximum AND
  // value of all the subsets having length K
  static int maxAndSubset(int arr[], int N, int K)
  {
     
    //Initializing the optimal_set
    ArrayList<Integer> optimal_set = new ArrayList<Integer>(N);
    for(int i = 0; i < N; i++){
      optimal_set.add(arr[i]);
    }
 
    // Iterating for every position of bits
    for (int j = 30; j >= 0; j--) {
      ArrayList<Integer> new_optimal_set = new ArrayList<Integer>();
 
      // Checking if the bits at jth
      // position can be obtained set
      // among the numbers available
      // from optimal_set set
      for (int element : optimal_set) {
        if (((1 << j) & element) == 0) {
 
          // If bit set at position j,
          // add into new_optimal_set
          new_optimal_set.add(element);
        }
      }
      if (new_optimal_set.size() < K)
        continue;
 
      // Updating optimal_set with new_optimal_set
      optimal_set = new_optimal_set;
      if (optimal_set.size() == K)
        break;
    }
 
    int ans = (1 << 30) - 1;
 
    for (int element : optimal_set) {
      ans &= element;
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int arr[] = { 7, 8, 9, 10, 11, 12 };
    int N = arr.length;
    int K = 3;
    System.out.println(maxAndSubset(arr, N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# python3 program for the above approach
 
# Function to find the maximum AND
# value of all the subsets having length K
def maxAndSubset(arr, N, K):
 
    # Initializing the optimal_set
    optimal_set = arr.copy()
 
    # Iterating for every position of bits
    for j in range(30, -1, -1):
        new_optimal_set = []
 
        # Checking if the bits at jth
        # position can be obtained set
        # among the numbers available
        # from optimal_set set
        for element in optimal_set:
            if ((1 << j) & element):
 
                # If bit set at position j,
                # add into new_optimal_set
                new_optimal_set.append(element)
 
        if (len(new_optimal_set) < K):
            continue
 
        # Updating optimal_set with new_optimal_set
        optimal_set = new_optimal_set
        if (len(optimal_set) == K):
            break
 
    ans = (1 << 30) - 1
 
    for element in optimal_set:
        ans &= element
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    arr = [7, 8, 9, 10, 11, 12]
    N = len(arr)
    K = 3
    print(maxAndSubset(arr, N, K))
 
  # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections;
class GFG
{
 
  // Function to find the maximum AND
  // value of all the subsets having length K
  static int maxAndSubset(int []arr, int N, int K)
  {
     
    // Initializing the optimal_set
    ArrayList optimal_set = new ArrayList(N);
    for(int i = 0; i < N; i++){
      optimal_set.Add(arr[i]);
    }
 
    // Iterating for every position of bits
    for (int j = 30; j >= 0; j--) {
      ArrayList new_optimal_set = new ArrayList();
 
      // Checking if the bits at jth
      // position can be obtained set
      // among the numbers available
      // from optimal_set set
      foreach (int element in optimal_set) {
        if (((1 << j) & element) == 0) {
 
          // If bit set at position j,
          // add into new_optimal_set
          new_optimal_set.Add(element);
        }
      }
      if (new_optimal_set.Count < K)
        continue;
 
      // Updating optimal_set with new_optimal_set
      optimal_set = new_optimal_set;
      if (optimal_set.Count == K)
        break;
    }
 
    int ans = (1 << 30) - 1;
 
    foreach (int element in optimal_set) {
      ans &= element;
    }
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int []arr = { 7, 8, 9, 10, 11, 12 };
    int N = arr.Length;
    int K = 3;
    Console.WriteLine(maxAndSubset(arr, N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
       // JavaScript code for the above approach
 
       // Function to find the maximum AND
       // value of all the subsets having length K
       function maxAndSubset(arr, N, K)
       {
        
           // Initializing the optimal_set
           let optimal_set = [...arr];
 
           // Iterating for every position of bits
           for (let j = 30; j >= 0; j--) {
               let new_optimal_set = [];
 
               // Checking if the bits at jth
               // position can be obtained set
               // among the numbers available
               // from optimal_set set
               for (let element of optimal_set) {
                   if ((1 << j) & element) {
 
                       // If bit set at position j,
                       // add into new_optimal_set
                       new_optimal_set.push(element);
                   }
               }
               if (new_optimal_set.length < K)
                   continue;
 
               // Updating optimal_set with new_optimal_set
               optimal_set = new_optimal_set;
               if (optimal_set.length == K)
                   break;
           }
 
           let ans = (1 << 30) - 1;
 
           for (let element of optimal_set) {
               ans &= element;
           }
           return ans;
       }
 
       // Driver Code
       let arr = [7, 8, 9, 10, 11, 12];
       let N = arr.length;
       let K = 3;
       document.write(maxAndSubset(arr, N, K));
 
      // This code is contributed by Potta Lokesh
   </script>
Producción: 

8

 

Complejidad temporal: O(32 * N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *