Minimice las eliminaciones en un Array determinado para que el máximo sea menos del doble del mínimo

Dada una array de enteros arr[] . La tarea es minimizar el número de eliminaciones requeridas de modo que el elemento máximo en arr[] sea menos del doble del mínimo.

Ejemplos

Entrada: arr[] = {4, 6, 21, 7, 5, 9, 12}
Salida: el número mínimo de operaciones de eliminación es 4.
Explicación: la array recién recortada es [7, 5, 9] donde 9 es el máximo y 5 es min; 9 < 2 × 5.

Entrada: arr[] = {14, 21, 62, 43, 39, 57}
Salida: el número mínimo de operaciones de eliminación es 2.
Explicación: la array recién recortada es [62, 43, 39, 57] 
donde 62 es el máximo y 39 es min; 62 < 2 × 39.

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . El pensamiento es muy simple y efectivo, considere el problema como encontrar el subarreglo más grande cuyo elemento máximo sea menos del doble del mínimo en lugar de eliminar elementos del arreglo. Siga los pasos a continuación para resolver el problema dado. 

• Atraviese el arreglo dado de izquierda a derecha y considere cada elemento como el punto de inicio del subarreglo.
• Con el índice de inicio elegido del subarreglo, elija con avidez el otro extremo del subarreglo en la medida de lo posible.
• Expanda el subarreglo a la derecha, un elemento a la vez, de modo que el elemento recién agregado satisfaga la condición dada.
• Siga el mismo proceso para todos los subarreglos para encontrar el subarreglo de tamaño máximo.
• La diferencia entre el tamaño del subarreglo y el arreglo de entrada será el número mínimo de eliminaciones necesarias.

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

// C++ program for above approach
#include <iostream>
using namespace std;
 
// Function to return minimum
int Min(int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}
 
// Function to return maximum
int Max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}
 
// Function to find minimum removal operations.
int findMinRemovals(int arr[], int n)
{
    // Stores the length of the maximum
    // size subarray
    int max_range = 0;
 
    // To keep track of the minimum and
    // the maximum elements
    // in a subarray
    int minimum, maximum;
 
    // Traverse the array and consider
    // each element as a
    // starting point of a subarray
    for (int i = 0; i < n && n - i >
         max_range; i++) {
        // Reset the minimum and the
        // maximum elements
        minimum = maximum = arr[i];
 
        // Find the maximum size subarray
        // `arr[i…j]`
        for (int j = i; j < n; j++) {
            // Find the minimum and the
            // maximum elements in the current
            // subarray. We must do this in
            // constant time.
            minimum = Min(minimum, arr[j]);
            maximum = Max(maximum, arr[j]);
 
            // Discard the subarray if the
            // invariant is violated
            if (2 * minimum <= maximum) {
                break;
            }
 
            // Update `max_range` when a
            // bigger subarray is found
            max_range = Max(max_range, j - i + 1);
        }
    }
 
    // Return array size - length of
    // the maximum size subarray
    return n - max_range;
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 6, 21, 7, 5, 9, 12 };
    int N = sizeof(arr) / sizeof(int);
 
    int res = findMinRemovals(arr, N);
 
    // Print the result
    cout << res;
 
    return 0;
}

// Java program for above approach
class GFG {
 
  // Function to return minimum
  static int Min(int a, int b) {
    if (a < b)
      return a;
    else
      return b;
  }
 
  // Function to return maximum
  static int Max(int a, int b) {
    if (a > b)
      return a;
    else
      return b;
  }
 
  // Function to find minimum removal operations.
  static int findMinRemovals(int arr[], int n)
  {
     
    // Stores the length of the maximum
    // size subarray
    int max_range = 0;
 
    // To keep track of the minimum and
    // the maximum elements
    // in a subarray
    int minimum, maximum;
 
    // Traverse the array and consider
    // each element as a
    // starting point of a subarray
    for (int i = 0; i < n && n - i > max_range; i++) {
      // Reset the minimum and the
      // maximum elements
      minimum = maximum = arr[i];
 
      // Find the maximum size subarray
      // `arr[i…j]`
      for (int j = i; j < n; j++) {
        // Find the minimum and the
        // maximum elements in the current
        // subarray. We must do this in
        // constant time.
        minimum = Min(minimum, arr[j]);
        maximum = Max(maximum, arr[j]);
 
        // Discard the subarray if the
        // invariant is violated
        if (2 * minimum <= maximum) {
          break;
        }
 
        // Update `max_range` when a
        // bigger subarray is found
        max_range = Max(max_range, j - i + 1);
      }
    }
 
    // Return array size - length of
    // the maximum size subarray
    return n - max_range;
  }
 
  // Driver Code
  public static void main(String args[]) {
    int arr[] = { 4, 6, 21, 7, 5, 9, 12 };
    int N = arr.length;
 
    int res = findMinRemovals(arr, N);
 
    // Print the result
    System.out.println(res);
  }
}
 
// This code is contributed by gfgking.

# python3 program for above approach
 
# Function to return minimum
def Min(a, b):
 
    if (a < b):
        return a
    else:
        return b
 
# Function to return maximum
def Max(a, b):
 
    if (a > b):
        return a
    else:
        return b
 
# Function to find minimum removal operations.
def findMinRemovals(arr, n):
 
    # Stores the length of the maximum
    # size subarray
    max_range = 0
     
    # To keep track of the minimum and
    # the maximum elements
    # in a subarray
 
    # Traverse the array and consider
    # each element as a
    # starting point of a subarray
    for i in range(0, n):
        if n - i <= max_range:
            break
             
        # Reset the minimum and the
        # maximum elements
        minimum = arr[i]
        maximum = arr[i]
 
        # Find the maximum size subarray
        # `arr[i…j]`
        for j in range(i, n):
            # Find the minimum and the
            # maximum elements in the current
            # subarray. We must do this in
            # constant time.
            minimum = Min(minimum, arr[j])
            maximum = Max(maximum, arr[j])
 
            # Discard the subarray if the
            # invariant is violated
            if (2 * minimum <= maximum):
                break
 
                # Update `max_range` when a
                # bigger subarray is found
            max_range = Max(max_range, j - i + 1)
 
        # Return array size - length of
        # the maximum size subarray
    return n - max_range
 
# Driver Code
if __name__ == "__main__":
 
    arr = [4, 6, 21, 7, 5, 9, 12]
    N = len(arr)
 
    res = findMinRemovals(arr, N)
 
    # Print the result
    print(res)
 
    # This code is contributed by rakeshsahni

// C# program for above approach
using System;
 
class GFG {
 
    // Function to return minimum
    static int Min(int a, int b)
    {
        if (a < b)
            return a;
        else
            return b;
    }
 
    // Function to return maximum
    static int Max(int a, int b)
    {
        if (a > b)
            return a;
        else
            return b;
    }
 
    // Function to find minimum removal operations.
    static int findMinRemovals(int[] arr, int n)
    {
 
        // Stores the length of the maximum
        // size subarray
        int max_range = 0;
 
        // To keep track of the minimum and
        // the maximum elements
        // in a subarray
        int minimum, maximum;
 
        // Traverse the array and consider
        // each element as a
        // starting point of a subarray
        for (int i = 0; i < n && n - i > max_range; i++) {
            // Reset the minimum and the
            // maximum elements
            minimum = maximum = arr[i];
 
            // Find the maximum size subarray
            // `arr[i…j]`
            for (int j = i; j < n; j++) {
                // Find the minimum and the
                // maximum elements in the current
                // subarray. We must do this in
                // constant time.
                minimum = Min(minimum, arr[j]);
                maximum = Max(maximum, arr[j]);
 
                // Discard the subarray if the
                // invariant is violated
                if (2 * minimum <= maximum) {
                    break;
                }
 
                // Update `max_range` when a
                // bigger subarray is found
                max_range = Max(max_range, j - i + 1);
            }
        }
 
        // Return array size - length of
        // the maximum size subarray
        return n - max_range;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 4, 6, 21, 7, 5, 9, 12 };
        int N = arr.Length;
 
        int res = findMinRemovals(arr, N);
 
        // Print the result
        Console.WriteLine(res);
    }
}
 
// This code is contributes by ukasp.

<script>
 
// JavaScript program for above approach
 
// Function to return minimum
function Min(a, b)
{
    if (a < b)
        return a;
    else
        return b;
}
 
// Function to return maximum
function Max(a, b)
{
    if (a > b)
        return a;
    else
        return b;
}
 
// Function to find minimum removal operations.
function findMinRemovals(arr, n)
{
     
    // Stores the length of the maximum
    // size subarray
    let max_range = 0;
 
    // To keep track of the minimum and
    // the maximum elements
    // in a subarray
    let minimum, maximum;
 
    // Traverse the array and consider
    // each element as a
    // starting point of a subarray
    for(let i = 0; i < n && n - i > max_range; i++)
    {
         
        // Reset the minimum and the
        // maximum elements
        minimum = maximum = arr[i];
 
        // Find the maximum size subarray
        // `arr[i…j]`
        for(let j = i; j < n; j++)
        {
             
            // Find the minimum and the
            // maximum elements in the current
            // subarray. We must do this in
            // constant time.
            minimum = Min(minimum, arr[j]);
            maximum = Max(maximum, arr[j]);
 
            // Discard the subarray if the
            // invariant is violated
            if (2 * minimum <= maximum)
            {
                break;
            }
 
            // Update `max_range` when a
            // bigger subarray is found
            max_range = Max(max_range, j - i + 1);
        }
    }
 
    // Return array size - length of
    // the maximum size subarray
    return n - max_range;
}
 
// Driver Code
let arr = [ 4, 6, 21, 7, 5, 9, 12 ];
let N = arr.length;
 
let res = findMinRemovals(arr, N);
 
// Print the result
document.write(res);
 
// This code is contributed by Potta Lokesh
 
</script>

4

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