Minimice el recuento de elementos de array que se eliminarán para maximizar la diferencia entre cualquier par hasta K

Dada una array arr[] y un entero K , la tarea es contar el número de elementos que se eliminarán de la array de modo que la diferencia entre el número máximo y mínimo que queda no exceda K.

Ejemplos:

Entrada: K = 1, arr[] = {1, 2, 3, 4, 5} 
Salida: 3 
Explicación: 
La eliminación de {5, 4, 3} modifica la array a {1, 2} donde la diferencia máxima es 1( =K).
Entrada: K = 3, arr[] = {1, 2, 3, 4, 5} 
Salida: 1 
Explicación: 
La eliminación de {5} modifica la array a {1, 2, 3, 4} donde la diferencia máxima es 3( =K).

Enfoque: 
la tarea es encontrar la diferencia entre el elemento de array máximo y mínimo que no debe exceder K .

• Ordene la array en orden ascendente e inicialice una variable a un valor mínimo.
• Iterar sobre la array para generar todos los pares posibles y verificar si la diferencia entre cualquier par es menor o igual a K .
• Actualice el número mínimo de eliminaciones para cada par.
• Finalmente, imprime las remociones mínimas obtenidas.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of
// elements to be removed from the
// array based on the given condition
int min_remove(int arr[], int n, int k)
{
    // Sort the array
    sort(arr, arr + n);
 
    /// Initialize the variable
    int ans = INT_MAX;
 
    // Iterate for all possible pairs
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
 
            // Check the difference
            // between the numbers
            if (arr[j] - arr[i] <= k) {
 
                // Update the minimum removals
                ans = min(ans, n - j + i - 1);
            }
        }
    }
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    int k = 3;
    int arr[] = { 1, 2, 3, 4, 5 };
 
    int n = sizeof arr / sizeof arr[0];
 
    cout << min_remove(arr, n, k);
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to count the number of
// elements to be removed from the
// array based on the given condition
static int min_remove(int arr[], int n, int k)
{
    // Sort the array
    Arrays.sort(arr);
 
    /// Initialize the variable
    int ans = Integer.MAX_VALUE;
 
    // Iterate for all possible pairs
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
 
            // Check the difference
            // between the numbers
            if (arr[j] - arr[i] <= k)
            {
 
                // Update the minimum removals
                ans = Math.min(ans, n - j + i - 1);
            }
        }
    }
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int k = 3;
    int arr[] = { 1, 2, 3, 4, 5 };
 
    int n = arr.length;
 
    System.out.print(min_remove(arr, n, k));
}
}
 
// This code is contributed by sapnasingh4991

# Python3 program to implement
# the above approach
import sys
 
# Function to count the number of
# elements to be removed from the
# array based on the given condition
def min_remove(arr, n, k):
 
    # Sort the array
    arr.sort()
 
    # Initialize the variable
    ans = sys.maxsize
 
    # Iterate for all possible pairs
    for i in range(n):
        for j in range(i, n):
 
            # Check the difference
            # between the numbers
            if (arr[j] - arr[i] <= k):
 
                # Update the minimum removals
                ans = min(ans, n - j + i - 1)
     
    # Return the answer
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    k = 3
    arr = [ 1, 2, 3, 4, 5 ]
 
    n = len(arr)
 
    print (min_remove(arr, n, k))
 
# This code is contributed by chitranayal

// C# Program to implement
// the above approach
using System;
class GFG{
 
// Function to count the number of
// elements to be removed from the
// array based on the given condition
static int min_remove(int []arr, int n, int k)
{
    // Sort the array
    Array.Sort(arr);
 
    /// Initialize the variable
    int ans = int.MaxValue;
 
    // Iterate for all possible pairs
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
 
            // Check the difference
            // between the numbers
            if (arr[j] - arr[i] <= k)
            {
 
                // Update the minimum removals
                ans = Math.Min(ans, n - j + i - 1);
            }
        }
    }
    // Return the answer
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int k = 3;
    int []arr = { 1, 2, 3, 4, 5 };
 
    int n = arr.Length;
 
    Console.Write(min_remove(arr, n, k));
}
}
 
// This code is contributed by sapnasingh4991

<script>
// JavaScript program for the above approach
 
// Function to count the number of
// elements to be removed from the
// array based on the given condition
function min_remove(arr, n, k)
{
    // Sort the array
    arr.sort();
   
    /// Initialize the variable
    let ans = Number.MAX_VALUE;
   
    // Iterate for all possible pairs
    for (let i = 0; i < n; i++)
    {
        for (let j = i; j < n; j++)
        {
   
            // Check the difference
            // between the numbers
            if (arr[j] - arr[i] <= k)
            {
   
                // Update the minimum removals
                ans = Math.min(ans, n - j + i - 1);
            }
        }
    }
    // Return the answer
    return ans;
}
       
// Driver Code
     
    let k = 3;
    let arr = [ 1, 2, 3, 4, 5 ];
   
    let n = arr.length;
   
    document.write(min_remove(arr, n, k));
                 
</script>

1

Complejidad de Tiempo: O(N ² ) 
Espacio Auxiliar: O(1)