Mínimo bit a bit O después de eliminar como máximo K elementos de la array dada

Dada una array A[] de longitud N , la tarea es encontrar el valor mínimo posible de OR bit a bit de los elementos después de eliminar como máximo K elementos.

Ejemplos: 

Entrada: A = {1, 10, 9, 4, 5, 16, 8}, K = 3
Salida: 11
Explicación: elimine 4, 5, 16 para la array dada.
Los elementos restantes son {1, 10, 9, 5}. 
Los OR de estos elementos son 11 que es el mínimo posible.

Entrada: A = {1, 2, 4, 8}, K = 1
Salida: 7
Explicación: Quite 8 de la array, mínimo OR= 1 | 2 | 4 = 7

Enfoque: este problema se puede resolver mediante la manipulación de bits sobre la base de la siguiente idea:

Intente eliminar primero los elementos MSB más altos, luego los elementos que tengan el segundo MSB más alto y así sucesivamente hasta que se eliminen los elementos K.

Siga la ilustración dada a continuación para una mejor comprensión.

Ilustración :

Considere A[] = [1, 10, 9, 4, 5, 16, 8]

• La representación binaria de los elementos es:
  1 – 00001
  10 – 01010
  9 – 01001
  4 – 00100
  5 – 00101
  16 – 10000
  8 – 01000
• Las posiciones del MSB de cada elemento son:
  1 -> 0, 10 -> 3, 9 -> 3, 4 -> 2, 5 -> 2, 16 -> 4, 8 -> 3
• Por lo tanto, el recuento de elementos que tienen MSB en la i-ésima posición es el siguiente:
  setBitCount = [1, 0, 2, 3, 1]
  Posición MSB 0, 1, 2, 3, 4
• Recorra la array y verifique si el setBitCount actual es menor que k, luego elimine todos los elementos con Bit actual como FirstSetBit.
  Para, K = 3, recorrer la array: 
  =>Cuando i = 4 : setBitCount[i] = 1, que es menor que K, así que elimine 16 , y ahora K = 2.
  =>Cuando i = 3 : K < setBitCount[i ] (es decir, 3). Así que no lo quites.
  =>Cuando i = 2 : setBitCount[i] = 2 ≤ K, así que elimine 4 y 5 . Ahora, K = 0.
• Calcular OR para todos los elementos restantes, es decir (1, 5, 9, 10) = 11

Siga los pasos mencionados a continuación para implementar la observación anterior:

• Crear una array hash .
• Recorra la array dada e incremente el índice MSB de cada elemento en la array hash.
• Ahora, recorra la array hash desde MSB y en cada iteración:
  • Compruebe si es posible eliminar todos los elementos que tengan el i-ésimo bit como MSB, es decir, setBitCount ≤ K.
  • Si setBitCount ≤ K, no calcule OR para esos elementos y simplemente reduzca la K.
  • si no, calcule el OR para elementos con i-ésimo bit como MSB.
• Devuelva Calcular OR después de eliminar K elementos.

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

// C++ program to find Minimum bitwise OR
// after removing at most K elements.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum possible OR
int minimumOR(vector<int> A, int N, int K)
{
    vector<int> SetBitCount(32, 0);
    int OR = 0, FirstSetBit = 0;
 
    // Sort in reverse order
    sort(A.rbegin(), A.rend());
    for (int i = 0; i < N; i++) {
        FirstSetBit = log2(A[i]) + 1;
        SetBitCount[FirstSetBit]++;
    }
 
    // Traverse from MSB to LSB
    for (int i = 31, j = 0; i >= 0; i--) {
        if (SetBitCount[i] <= K) {
            K -= SetBitCount[i];
            j += SetBitCount[i];
        }
        else {
            for (int x = j;
                 j < x + SetBitCount[i]; j++)
                OR = OR | A[j];
        }
    }
 
    return OR;
}
 
// Driver code
int main()
{
    int N = 7;
    vector<int> A = { 1, 10, 9, 4, 5, 16, 8 };
    int K = 3;
 
    cout << minimumOR(A, N, K);
    return 0;
}

// Java program to find Minimum bitwise OR
// after removing at most K elements.
import java.util.*;
public class GFG
{
 
  // Function to reverse an array
  static void reverse(int a[], int n)
  {
    int i, k, t;
    for (i = 0; i < n / 2; i++) {
      t = a[i];
      a[i] = a[n - i - 1];
      a[n - i - 1] = t;
    }
  }
 
  // Function to find the minimum possible OR
  static int minimumOR(int[] A, int N, int K)
  {
    int[] SetBitCount = new int[32];
    for (int i = 0; i < 32; i++) {
      SetBitCount[i] = 0;
    }
    int OR = 0, FirstSetBit = 0;
 
    // Sort array in ascending order.
    Arrays.sort(A);
    // reverse array
    reverse(A, N);
 
    for (int i = 0; i < N; i++) {
      FirstSetBit
        = (int)(Math.log(A[i]) / Math.log(2)) + 1;
      SetBitCount[FirstSetBit]++;
    }
 
    // Traverse from MSB to LSB
    for (int i = 31, j = 0; i >= 0; i--) {
      if (SetBitCount[i] <= K) {
        K -= SetBitCount[i];
        j += SetBitCount[i];
      }
      else {
        for (int x = j; j < x + SetBitCount[i]; j++)
          OR = (OR | A[j]);
      }
    }
 
    return OR;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int N = 7;
    int[] A = { 1, 10, 9, 4, 5, 16, 8 };
    int K = 3;
 
    System.out.println(minimumOR(A, N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python program to find Minimum bitwise OR
# after removing at most K elements.
import math
 
# Function to find the minimum possible OR
def minimumOR(A, N, K):
 
    SetBitCount = [0] * 32
    OR = 0
    FirstSetBit = 0
 
    # Sort in reverse order
    A.sort(reverse=True)
 
    for i in range(0, N):
 
        FirstSetBit = int(math.log(A[i], 2)) + 1
        SetBitCount[FirstSetBit] += 1
 
    # Traverse from MSB to LSB
    j = 0
    i = 31
    while(i >= 0):
        if (SetBitCount[i] <= K):
            K -= SetBitCount[i]
            j += SetBitCount[i]
 
        else:
            x = j
            while(j < x + SetBitCount[i]):
                OR = OR | A[j]
                j += 1
 
        i -= 1
 
    return OR
 
# Driver code
N = 7
A = [1, 10, 9, 4, 5, 16, 8]
K = 3
 
print(minimumOR(A, N, K))
 
# This code is contributed by Samim Hossainn Mondal.

// C# program to find Minimum bitwise OR
// after removing at most K elements.
using System;
class GFG {
 
  // Function to find the minimum possible OR
  static int minimumOR(int[] A, int N, int K)
  {
    int[] SetBitCount = new int[32];
    for (int i = 0; i < 32; i++) {
      SetBitCount[i] = 0;
    }
    int OR = 0, FirstSetBit = 0;
 
    // Sort array in ascending order.
    Array.Sort(A);
    // reverse array
    Array.Reverse(A);
 
    for (int i = 0; i < N; i++) {
      FirstSetBit = (int)Math.Log(A[i], 2) + 1;
      SetBitCount[FirstSetBit]++;
    }
 
    // Traverse from MSB to LSB
    for (int i = 31, j = 0; i >= 0; i--) {
      if (SetBitCount[i] <= K) {
        K -= SetBitCount[i];
        j += SetBitCount[i];
      }
      else {
        for (int x = j; j < x + SetBitCount[i]; j++)
          OR = (OR | A[j]);
      }
    }
 
    return OR;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 7;
    int[] A = { 1, 10, 9, 4, 5, 16, 8 };
    int K = 3;
 
    Console.Write(minimumOR(A, N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find the minimum possible OR
       function minimumOR(A, N, K) {
           let SetBitCount = new Array(32).fill(0);
           let OR = 0, FirstSetBit = 0;
 
           // Sort in reverse order
           A.sort(function (a, b) { return b - a })
           for (let i = 0; i < N; i++) {
               FirstSetBit = Math.log2(A[i]) + 1;
               SetBitCount[FirstSetBit]++;
           }
 
           // Traverse from MSB to LSB
           for (let i = 31, j = 0; i >= 0; i--) {
               if (SetBitCount[i] <= K) {
                   K -= SetBitCount[i];
                   j += SetBitCount[i];
               }
               else {
                   for (let x = j;
                       j < x + SetBitCount[i]; j++)
                       OR = OR | A[j];
               }
           }
 
           return OR;
       }
 
       // Driver code
       let N = 7;
       let A = [1, 10, 9, 4, 5, 16, 8]
       let K = 3;
 
       document.write(minimumOR(A, N, K));
 
    // This code is contributed by Potta Lokesh
   </script>

11

Complejidad de tiempo: O(N* log(N))
Espacio auxiliar: O(N)