Elimine los números mínimos de la array para obtener el valor OR mínimo

Dada una array arr[] de N enteros positivos, la tarea es encontrar el número mínimo de elementos que se eliminarán de la array para que el OR bit a bit de los elementos de la array se minimice. No se le permite eliminar todos los elementos, es decir, al menos un elemento debe permanecer en la array.
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3} 
Salida: 2 
Todos los subconjuntos posibles y sus valores OR son: 
a) {1, 2, 3} = 3 
b) {1, 2} = 3 
c) {2, 3} = 3 
d) {1, 3} = 3 
e) {1} = 1 
f) {2} = 2 
g) {3} = 3 
El mínimo OR posible será 1 del subconjunto {1}. 
Entonces, tendremos que eliminar 2 elementos.
Entrada: arr[] = {3, 3, 3} 
Salida: 0 
 

Enfoque ingenuo: genere todas las subsecuencias posibles y pruebe cuál da el valor mínimo de ‘O’. Sea L la longitud de la subsecuencia más grande con el mínimo O posible, entonces la respuesta será N – L. Esto tomará un tiempo exponencial.
Mejor enfoque: el valor mínimo siempre será igual al número más pequeño presente en la array. Si este número obtiene OR bit a bit con cualquier otro número que no sea él mismo, entonces el valor de OR cambiará y ya no será mínimo. Por lo tanto, debemos eliminar todos los elementos que no sean iguales a este elemento mínimo. 
 

• Encuentra el número más pequeño en la array.
• Encuentre la frecuencia de este elemento en la array, digamos cnt .
• La respuesta final será N – cnt .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// deletions to get minimum OR
int findMinDel(int* arr, int n)
{
 
    // To store the minimum element
    int min_num = INT_MAX;
 
    // Find the minimum element
    // from the array
    for (int i = 0; i < n; i++)
        min_num = min(arr[i], min_num);
 
    // To store the frequency of
    // the minimum element
    int cnt = 0;
 
    // Find the frequency of the
    // minimum element
    for (int i = 0; i < n; i++)
        if (arr[i] == min_num)
            cnt++;
 
    // Return the final answer
    return n - cnt;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 3, 2 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << findMinDel(arr, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the minimum
// deletions to get minimum OR
static int findMinDel(int []arr, int n)
{
 
    // To store the minimum element
    int min_num = Integer.MAX_VALUE;
 
    // Find the minimum element
    // from the array
    for (int i = 0; i < n; i++)
        min_num = Math.min(arr[i], min_num);
 
    // To store the frequency of
    // the minimum element
    int cnt = 0;
 
    // Find the frequency of the
    // minimum element
    for (int i = 0; i < n; i++)
        if (arr[i] == min_num)
            cnt++;
 
    // Return the final answer
    return n - cnt;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 3, 2 };
    int n = arr.length;
 
    System.out.print(findMinDel(arr, n));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
import sys
 
# Function to return the minimum
# deletions to get minimum OR
def findMinDel(arr, n) :
 
    # To store the minimum element
    min_num = sys.maxsize;
 
    # Find the minimum element
    # from the array
    for i in range(n) :
        min_num = min(arr[i], min_num);
 
    # To store the frequency of
    # the minimum element
    cnt = 0;
 
    # Find the frequency of the
    # minimum element
    for i in range(n) :
        if (arr[i] == min_num) :
            cnt += 1;
 
    # Return the final answer
    return n - cnt;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 3, 3, 2 ];
    n = len(arr);
     
    print(findMinDel(arr, n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the minimum
// deletions to get minimum OR
static int findMinDel(int []arr, int n)
{
 
    // To store the minimum element
    int min_num = int.MaxValue;
 
    // Find the minimum element
    // from the array
    for (int i = 0; i < n; i++)
        min_num = Math.Min(arr[i],
                           min_num);
 
    // To store the frequency of
    // the minimum element
    int cnt = 0;
 
    // Find the frequency of the
    // minimum element
    for (int i = 0; i < n; i++)
        if (arr[i] == min_num)
            cnt++;
 
    // Return the readonly answer
    return n - cnt;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 3, 2 };
    int n = arr.Length;
 
    Console.Write(findMinDel(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to return the minimum
// deletions to get minimum OR
function findMinDel(arr, n)
{
 
    // To store the minimum element
    var min_num = 1000000000;
 
    // Find the minimum element
    // from the array
    for (var i = 0; i < n; i++)
        min_num = Math.min(arr[i], min_num);
 
    // To store the frequency of
    // the minimum element
    var cnt = 0;
 
    // Find the frequency of the
    // minimum element
    for (var i = 0; i < n; i++)
        if (arr[i] == min_num)
            cnt++;
 
    // Return the final answer
    return n - cnt;
}
 
// Driver code
var arr = [3, 3, 2];
var n = arr.length;
document.write( findMinDel(arr, n));
 
// This code is contributed by noob2000.
</script>

2

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)