Dados N enteros y K, encuentre el número mínimo de elementos que deben eliminarse, tal que A max -A min <=K. Después de la eliminación de elementos, A max y A min se consideran entre los elementos restantes.
Ejemplos:
Input : a[] = {1, 3, 4, 9, 10, 11, 12, 17, 20}
k = 4
Output : 5
Explanation: Remove 1, 3, 4 from beginning
and 17, 20 from the end.
Input : a[] = {1, 5, 6, 2, 8} K=2
Output : 3
Explanation: There are multiple ways to
remove elements in this case.
One among them is to remove 5, 6, 8.
The other is to remove 1, 2, 5
Planteamiento: Ordenar los elementos dados. Usando el enfoque codicioso, la mejor manera es eliminar el elemento mínimo o el elemento máximo y luego verificar si A max -A min <= K . Hay varias combinaciones de remociones que deben ser consideradas. Escribimos una relación de recurrencia para probar todas las combinaciones posibles. Habrá dos formas posibles de eliminación, o eliminamos el mínimo o eliminamos el máximo. Sea (i…j) el índice de elementos que quedan después de la eliminación de elementos . Inicialmente, comenzamos con i=0 y j=n-1 y el número de elementos eliminados es 0 al principio. Solo eliminamos un elemento si a[j]-a[i]>k, las dos posibles formas de eliminación son (i+1…j) o (i…j-1). Se considera el mínimo de los dos.
Sea DP i, j el número de elementos que deben eliminarse para que después de la eliminación a[j]-a[i]<=k.
Relación de recurrencia para array ordenada:
DPi, j = 1+ (min(countRemovals(i+1, j), countRemovals(i, j-1))
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to find minimum removals
// to make max-min <= K
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
int dp[MAX][MAX];
// function to check all possible combinations
// of removal and return the minimum one
int countRemovals(int a[], int i, int j, int k)
{
// base case when all elements are removed
if (i >= j)
return 0;
// if condition is satisfied, no more
// removals are required
else if ((a[j] - a[i]) <= k)
return 0;
// if the state has already been visited
else if (dp[i][j] != -1)
return dp[i][j];
// when Amax-Amin>d
else if ((a[j] - a[i]) > k) {
// minimum is taken of the removal
// of minimum element or removal
// of the maximum element
dp[i][j] = 1 + min(countRemovals(a, i + 1, j, k),
countRemovals(a, i, j - 1, k));
}
return dp[i][j];
}
// To sort the array and return the answer
int removals(int a[], int n, int k)
{
// sort the array
sort(a, a + n);
// fill all stated with -1
// when only one element
memset(dp, -1, sizeof(dp));
if (n == 1)
return 0;
else
return countRemovals(a, 0, n - 1, k);
}
// Driver Code
int main()
{
int a[] = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
cout << removals(a, n, k);
return 0;
}
Java
// Java program to find minimum removals
// to make max-min <= K
import java.util.Arrays;
class GFG
{
static int MAX=100;
static int dp[][]=new int[MAX][MAX];
// function to check all possible combinations
// of removal and return the minimum one
static int countRemovals(int a[], int i, int j, int k)
{
// base case when all elements are removed
if (i >= j)
return 0;
// if condition is satisfied, no more
// removals are required
else if ((a[j] - a[i]) <= k)
return 0;
// if the state has already been visited
else if (dp[i][j] != -1)
return dp[i][j];
// when Amax-Amin>d
else if ((a[j] - a[i]) > k) {
// minimum is taken of the removal
// of minimum element or removal
// of the maximum element
dp[i][j] = 1 + Math.min(countRemovals(a, i + 1, j, k),
countRemovals(a, i, j - 1, k));
}
return dp[i][j];
}
// To sort the array and return the answer
static int removals(int a[], int n, int k)
{
// sort the array
Arrays.sort(a);
// fill all stated with -1
// when only one element
for(int[] rows:dp)
Arrays.fill(rows,-1);
if (n == 1)
return 0;
else
return countRemovals(a, 0, n - 1, k);
}
// Driver code
public static void main (String[] args)
{
int a[] = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = a.length;
int k = 4;
System.out.print(removals(a, n, k));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find # minimum removals to # make max-min <= K MAX = 100 dp = [[0 for i in range(MAX)] for i in range(MAX)] for i in range(0, MAX) : for j in range(0, MAX) : dp[i][j] = -1 # function to check all # possible combinations # of removal and return # the minimum one def countRemovals(a, i, j, k) : global dp # base case when all # elements are removed if (i >= j) : return 0 # if condition is satisfied, # no more removals are required elif ((a[j] - a[i]) <= k) : return 0 # if the state has # already been visited elif (dp[i][j] != -1) : return dp[i][j] # when Amax-Amin>d elif ((a[j] - a[i]) > k) : # minimum is taken of # the removal of minimum # element or removal of # the maximum element dp[i][j] = 1 + min(countRemovals(a, i + 1, j, k), countRemovals(a, i, j - 1, k)) return dp[i][j] # To sort the array # and return the answer def removals(a, n, k) : # sort the array a.sort() # fill all stated # with -1 when only # one element if (n == 1) : return 0 else : return countRemovals(a, 0, n - 1, k) # Driver Code a = [1, 3, 4, 9, 10, 11, 12, 17, 20] n = len(a) k = 4 print (removals(a, n, k)) # This code is contributed by # Manish Shaw(manishshaw1)
C#
// C# program to find minimum
// removals to make max-min <= K
using System;
class GFG
{
static int MAX = 100;
static int [,]dp = new int[MAX, MAX];
// function to check all
// possible combinations
// of removal and return
// the minimum one
static int countRemovals(int []a, int i,
int j, int k)
{
// base case when all
// elements are removed
if (i >= j)
return 0;
// if condition is satisfied,
// no more removals are required
else if ((a[j] - a[i]) <= k)
return 0;
// if the state has
// already been visited
else if (dp[i, j] != -1)
return dp[i, j];
// when Amax-Amin>d
else if ((a[j] - a[i]) > k)
{
// minimum is taken of the
// removal of minimum element
// or removal of the maximum
// element
dp[i, j] = 1 + Math.Min(countRemovals(a, i + 1,
j, k),
countRemovals(a, i,
j - 1, k));
}
return dp[i, j];
}
// To sort the array and
// return the answer
static int removals(int []a,
int n, int k)
{
// sort the array
Array.Sort(a);
// fill all stated with -1
// when only one element
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
dp[i, j] = -1;
}
if (n == 1)
return 0;
else
return countRemovals(a, 0,
n - 1, k);
}
// Driver code
static void Main()
{
int []a = new int[]{ 1, 3, 4, 9, 10,
11, 12, 17, 20 };
int n = a.Length;
int k = 4;
Console.Write(removals(a, n, k));
}
}
// This code is contributed by
// ManishShaw(manishshaw1)
PHP
<?php
// PHP program to find
// minimum removals to
// make max-min <= K
$MAX = 100;
$dp = array(array());
for($i = 0; $i < $MAX; $i++)
{
for($j = 0; $j < $MAX; $j++)
$dp[$i][$j] = -1;
}
// function to check all
// possible combinations
// of removal and return
// the minimum one
function countRemovals($a, $i,
$j, $k)
{
global $dp;
// base case when all
// elements are removed
if ($i >= $j)
return 0;
// if condition is satisfied,
// no more removals are required
else if (($a[$j] - $a[$i]) <= $k)
return 0;
// if the state has
// already been visited
else if ($dp[$i][$j] != -1)
return $dp[$i][$j];
// when Amax-Amin>d
else if (($a[$j] - $a[$i]) > $k)
{
// minimum is taken of
// the removal of minimum
// element or removal of
// the maximum element
$dp[$i][$j] = 1 + min(countRemovals($a, $i + 1,
$j, $k),
countRemovals($a, $i,
$j - 1, $k));
}
return $dp[$i][$j];
}
// To sort the array
// and return the answer
function removals($a, $n, $k)
{
// sort the array
sort($a);
// fill all stated with -1
// when only one element
if ($n == 1)
return 0;
else
return countRemovals($a, 0,
$n - 1, $k);
}
// Driver Code
$a = array(1, 3, 4, 9, 10,
11, 12, 17, 20);
$n = count($a);
$k = 4;
echo (removals($a, $n, $k));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// JavaScript program to find minimum removals
// to make max-min <= K
let MAX = 100;
let dp = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
dp[i] = new Array(MAX);
}
// function to check all possible combinations
// of removal and return the minimum one
function countRemovals(a,i,j,k)
{
// base case when all elements are removed
if (i >= j)
return 0;
// if condition is satisfied, no more
// removals are required
else if ((a[j] - a[i]) <= k)
return 0;
// if the state has already been visited
else if (dp[i][j] != -1)
return dp[i][j];
// when Amax-Amin>d
else if ((a[j] - a[i]) > k) {
// minimum is taken of the removal
// of minimum element or removal
// of the maximum element
dp[i][j] = 1 + Math.min(countRemovals(a, i + 1, j, k),
countRemovals(a, i, j - 1, k));
}
return dp[i][j];
}
// To sort the array and return the answer
function removals(a,n,k)
{
// sort the array
a.sort(function(a, b){return a - b});
// fill all stated with -1
// when only one element
for(let i = 0; i < MAX; i++)
{
for(let j = 0; j < MAX; j++)
{
dp[i][j] = -1;
}
}
if (n == 1)
return 0;
else
return countRemovals(a, 0, n - 1, k);
}
// Driver Code
let a = [ 1, 3, 4, 9, 10, 11, 12, 17, 20 ];
let n = a.length;
let k = 4;
document.write(removals(a, n, k));
</script>
Producción
5
Complejidad del Tiempo: O(n 2 )
Espacio Auxiliar: O(n 2 )
La solución podría optimizarse aún más. La idea es ordenar la array en orden creciente y atravesar todos los elementos (digamos índice i) y encontrar el elemento máximo a su derecha (índice j) tal que arr[j] – arr[i] <= k. Por lo tanto, el número de elementos a eliminar se convierte en n-(j-i+1). El número mínimo de elementos se puede encontrar tomando el mínimo de n-(ji-1) total i. El valor del índice j se puede encontrar mediante una búsqueda binaria entre inicio = i+1 y fin = n-1;
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find
// rightmost index
// which satisfies the condition
// arr[j] - arr[i] <= k
int findInd(int key, int i,
int n, int k, int arr[])
{
int start, end, mid, ind = -1;
// Initialising start to i + 1
start = i + 1;
// Initialising end to n - 1
end = n - 1;
// Binary search implementation
// to find the rightmost element
// that satisfy the condition
while (start < end)
{
mid = start + (end - start) / 2;
// Check if the condition satisfies
if (arr[mid] - key <= k)
{
// Store the position
ind = mid;
// Make start = mid + 1
start = mid + 1;
}
else
{
// Make end = mid
end = mid;
}
}
// Return the rightmost position
return ind;
}
// Function to calculate
// minimum number of elements
// to be removed
int removals(int arr[], int n, int k)
{
int i, j, ans = n - 1;
// Sort the given array
sort(arr, arr + n);
// Iterate from 0 to n-1
for (i = 0; i < n; i++)
{
// Find j such that
// arr[j] - arr[i] <= k
j = findInd(arr[i], i, n, k, arr);
// If there exist such j
// that satisfies the condition
if (j != -1)
{
// Number of elements
// to be removed for this
// particular case is
// (j - i + 1)
ans = min(ans, n - (j - i + 1));
}
}
// Return answer
return ans;
}
// Driver Code
int main()
{
int a[] = {1, 3, 4, 9, 10,
11, 12, 17, 20};
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
cout << removals(a, n, k);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find rightmost index
// which satisfies the condition
// arr[j] - arr[i] <= k
static int findInd(int key, int i,
int n, int k, int arr[])
{
int start, end, mid, ind = -1;
// Initialising start to i + 1
start = i + 1;
// Initialising end to n - 1
end = n - 1;
// Binary search implementation
// to find the rightmost element
// that satisfy the condition
while (start < end)
{
mid = start + (end - start) / 2;
// Check if the condition satisfies
if (arr[mid] - key <= k)
{
// Store the position
ind = mid;
// Make start = mid + 1
start = mid + 1;
}
else
{
// Make end = mid
end = mid;
}
}
// Return the rightmost position
return ind;
}
// Function to calculate
// minimum number of elements
// to be removed
static int removals(int arr[], int n, int k)
{
int i, j, ans = n - 1;
// Sort the given array
Arrays.sort(arr);
// Iterate from 0 to n-1
for(i = 0; i < n; i++)
{
// Find j such that
// arr[j] - arr[i] <= k
j = findInd(arr[i], i, n, k, arr);
// If there exist such j
// that satisfies the condition
if (j != -1)
{
// Number of elements
// to be removed for this
// particular case is
// (j - i + 1)
ans = Math.min(ans,
n - (j - i + 1));
}
}
// Return answer
return ans;
}
// Driver Code
public static void main(String args[])
{
int a[] = { 1, 3, 4, 9, 10,
11, 12, 17, 20 };
int n = a.length;
int k = 4;
System.out.println(removals(a, n, k));
}
}
// This code is contributed by adityapande88
Python3
# Python program for the # above approach # Function to find # rightmost index # which satisfies the condition # arr[j] - arr[i] <= k def findInd(key, i, n, k, arr): ind = -1 # Initialising start # to i + 1 start = i + 1 # Initialising end # to n - 1 end = n - 1; # Binary search implementation # to find the rightmost element # that satisfy the condition while (start < end): mid = int(start + (end - start) / 2) # Check if the condition # satisfies if (arr[mid] - key <= k): # Store the position ind = mid # Make start = mid + 1 start = mid + 1 else: # Make end = mid end = mid # Return the rightmost position return ind # Function to calculate # minimum number of elements # to be removed def removals(arr, n, k): ans = n - 1 # Sort the given array arr.sort() # Iterate from 0 to n-1 for i in range(0, n): # Find j such that # arr[j] - arr[i] <= k j = findInd(arr[i], i, n, k, arr) # If there exist such j # that satisfies the condition if (j != -1): # Number of elements # to be removed for this # particular case is # (j - i + 1) ans = min(ans, n - (j - i + 1)) # Return answer return ans # Driver Code a = [1, 3, 4, 9, 10,11, 12, 17, 20] n = len(a) k = 4 print(removals(a, n, k)) # This code is contributed by Stream_Cipher
C#
// C# program for the above approach
using System;
class GFG{
// Function to find rightmost index
// which satisfies the condition
// arr[j] - arr[i] <= k
static int findInd(int key, int i,
int n, int k, int[] arr)
{
int start, end, mid, ind = -1;
// Initialising start to i + 1
start = i + 1;
// Initialising end to n - 1
end = n - 1;
// Binary search implementation
// to find the rightmost element
// that satisfy the condition
while (start < end)
{
mid = start + (end - start) / 2;
// Check if the condition satisfies
if (arr[mid] - key <= k)
{
// Store the position
ind = mid;
// Make start = mid + 1
start = mid + 1;
}
else
{
// Make end = mid
end = mid;
}
}
// Return the rightmost position
return ind;
}
// Function to calculate minimum
// number of elements to be removed
static int removals(int[] arr, int n, int k)
{
int i, j, ans = n - 1;
// Sort the given array
Array.Sort(arr);
// Iterate from 0 to n-1
for(i = 0; i < n; i++)
{
// Find j such that
// arr[j] - arr[i] <= k
j = findInd(arr[i], i, n, k, arr);
// If there exist such j
// that satisfies the condition
if (j != -1)
{
// Number of elements
// to be removed for this
// particular case is
// (j - i + 1)
ans = Math.Min(ans,
n - (j - i + 1));
}
}
// Return answer
return ans;
}
// Driver code
static void Main()
{
int[] a = { 1, 3, 4, 9, 10,
11, 12, 17, 20 };
int n = a.Length;
int k = 4;
Console.Write(removals(a, n, k));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// javascript program for the above approach
// Function to find rightmost index
// which satisfies the condition
// arr[j] - arr[i] <= k
function findInd(key , i , n , k , arr) {
var start, end, mid, ind = -1;
// Initialising start to i + 1
start = i + 1;
// Initialising end to n - 1
end = n - 1;
// Binary search implementation
// to find the rightmost element
// that satisfy the condition
while (start < end) {
mid = start + (end - start) / 2;
// Check if the condition satisfies
if (arr[mid] - key <= k) {
// Store the position
ind = mid;
// Make start = mid + 1
start = mid + 1;
}
else {
// Make end = mid
end = mid;
}
}
// Return the rightmost position
return ind;
}
// Function to calculate
// minimum number of elements
// to be removed
function removals(arr , n , k) {
var i, j, ans = n - 1;
// Sort the given array
arr.sort((a,b)=>a-b);
// Iterate from 0 to n-1
for (i = 0; i < n; i++) {
// Find j such that
// arr[j] - arr[i] <= k
j = findInd(arr[i], i, n, k, arr);
// If there exist such j
// that satisfies the condition
if (j != -1) {
// Number of elements
// to be removed for this
// particular case is
// (j - i + 1)
ans = Math.min(ans, n - (j - i + 1));
}
}
// Return answer
return ans;
}
// Driver Code
var a = [ 1, 3, 4, 9, 10, 11, 12, 17, 20 ];
var n = a.length;
var k = 4;
document.write(removals(a, n, k));
// This code contributed by Rajput-Ji
</script>
Producción
5
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(n)
Acercarse:
- La solución podría optimizarse aún más. La idea es ordenar la array en orden creciente y recorrer todos los elementos (digamos índice j) y encontrar el elemento mínimo a su izquierda (índice i) tal que arr[j] – arr[i] <= k y almacenar en dp[j].
- Por lo tanto, el número de elementos a eliminar se convierte en n-(j-i+1). El número mínimo de elementos se puede encontrar tomando el mínimo de n-(ji-1) total j. El valor del índice i se puede encontrar a través de su valor de elemento de array dp anterior.
A continuación se muestra la implementación del enfoque:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// To sort the array and return the answer
int removals(int arr[], int n, int k)
{
// sort the array
sort(arr, arr + n);
int dp[n];
// fill all stated with -1
// when only one element
for(int i = 0; i < n; i++)
dp[i] = -1;
// as dp[0] = 0 (base case) so min
// no of elements to be removed are
// n-1 elements
int ans = n - 1;
dp[0] = 0;
for (int i = 1; i < n; i++)
{
dp[i] = i;
int j = dp[i - 1];
while (j != i && arr[i] - arr[j] > k)
{
j++;
}
dp[i] = min(dp[i], j);
ans = min(ans, (n - (i - j + 1)));
}
return ans;
}
// Driver code
int main()
{
int a[] = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
cout<<removals(a, n, k);
return 0;
}
// This code is contributed by Balu Nagar
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// To sort the array and return the answer
static int removals(int arr[], int n, int k)
{
// sort the array
Arrays.sort(arr);
// fill all stated with -1
// when only one element
int dp[] = new int[n];
Arrays.fill(dp, -1);
// as dp[0] = 0 (base case) so min
// no of elements to be removed are
// n-1 elements
int ans = n - 1;
dp[0] = 0;
// Iterate from 1 to n - 1
for (int i = 1; i < n; i++) {
dp[i] = i;
int j = dp[i - 1];
while (j != i && arr[i] - arr[j] > k) {
j++;
}
dp[i] = Integer.min(dp[i], j);
ans = Integer.min(ans, (n - (i - j + 1)));
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = a.length;
int k = 4;
System.out.print(removals(a, n, k));
}
}
Python3
# Python3 program for the above approach # To sort the array and return the answer def removals(arr, n, k): # sort the array arr.sort() dp = [0 for i in range(n)] # Fill all stated with -1 # when only one element for i in range(n): dp[i] = -1 # As dp[0] = 0 (base case) so min # no of elements to be removed are # n-1 elements ans = n - 1 dp[0] = 0 for i in range(1, n): dp[i] = i j = dp[i - 1] while (j != i and arr[i] - arr[j] > k): j += 1 dp[i] = min(dp[i], j) ans = min(ans, (n - (i - j + 1))) return ans # Driver code a = [ 1, 3, 4, 9, 10, 11, 12, 17, 20 ] n = len(a) k = 4 print(removals(a, n, k)) # This code is contributed by rohan07
C#
// C# program for the above approach
using System;
class GFG{
// To sort the array and return the answer
static int removals(int[] arr, int n, int k)
{
// Sort the array
Array.Sort(arr);
int[] dp = new int[n];
// Fill all stated with -1
// when only one element
for(int i = 0; i < n; i++)
dp[i] = -1;
// As dp[0] = 0 (base case) so min
// no of elements to be removed are
// n-1 elements
int ans = n - 1;
dp[0] = 0;
// Iterate from 1 to n - 1
for(int i = 1; i < n; i++)
{
dp[i] = i;
int j = dp[i - 1];
while (j != i && arr[i] - arr[j] > k)
{
j++;
}
dp[i] = Math.Min(dp[i], j);
ans = Math.Min(ans, (n - (i - j + 1)));
}
return ans;
}
// Driver code
static public void Main()
{
int[] a = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = a.Length;
int k = 4;
Console.Write(removals(a, n, k));
}
}
// This code is contributed by lokeshpotta20
Javascript
<script>
// JavaScript program for the above approach
// To sort the array and return the answer
function removals(arr, n, k)
{
// sort the array
arr.sort((a,b)=>a-b);
var dp = Array(n);
// fill all stated with -1
// when only one element
for(var i = 0; i < n; i++)
dp[i] = -1;
// as dp[0] = 0 (base case) so min
// no of elements to be removed are
// n-1 elements
var ans = n - 1;
dp[0] = 0;
for (var i = 1; i < n; i++)
{
dp[i] = i;
var j = dp[i - 1];
while (j != i && arr[i] - arr[j] > k)
{
j++;
}
dp[i] = Math.min(dp[i], j);
ans = Math.min(ans, (n - (i - j + 1)));
}
return ans;
}
// Driver code
var a = [1, 3, 4, 9, 10, 11, 12, 17, 20];
var n = a.length;
var k = 4;
document.write( removals(a, n, k));
</script>
Producción
5
Complejidad temporal : O(nlog n). Como bucle exterior va a hacer n iteraciones. Y el ciclo interno itera al máximo n veces para todas las iteraciones externas. Porque comenzamos el valor de j desde dp[i-1] y lo repetimos hasta que alcanza i y luego, para el siguiente elemento, comenzamos nuevamente desde el valor anterior de dp[i]. Entonces, la complejidad del tiempo total es O (n) si no consideramos la complejidad de la clasificación, ya que tampoco se considera en la solución anterior.
Espacio Auxiliar : O(n)
Enfoque de espacio optimizado
La solución podría optimizarse aún más. Se puede hacer en Espacio Auxiliar: O(1). La idea es ordenar primero la array en orden ascendente. Mantenga 2 punteros, digamos i y j, donde j itera desde el índice 1 al índice n-1 y realiza un seguimiento del subarreglo final con la diferencia en max y min menor que k, e i realiza un seguimiento del índice inicial del subarreglo. Si encontramos que a[j] – a[i[ <=k (significa que el subarreglo i a j es válido) actualizamos la longitud de i a j en una variable para rastrear la longitud máxima hasta el momento. De lo contrario, actualizamos el índice inicial i con i+1.
Al principio parece que se ignoran los subarreglos de i a j, pero obviamente sus longitudes son menores que las de los subarreglos de i a j, por lo que no nos preocupamos por ellos.
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
int removal(int a[], int n, int k)
{
// Sort the Array; Time complexity:O(nlogn)
sort(a, a + n);
// to store the max length of
// array with difference <= k
int maxLen = INT_MIN;
int i = 0;
// J goes from 1 to n-1 in n-2 iterations
// Thus time complexity of below loop is O(n)
for (int j = i + 1; j < n && i < n; j++) {
// if the subarray from i to j index is valid
// the store it's length
if (a[j] - a[i] <= k) {
maxLen = max(maxLen, j - i + 1);
}
// if subarray difference exceeds k
// change starting position, i.e. i
else {
i++;
}
}
// no. of elements need to be removed is
// Length of array - max subarray with diff <= k
int removed = n - maxLen;
return removed;
}
//Driver Code
int main()
{
int a[] = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
cout << removal(a, n, k);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
public static int removal(int[] a, int n, int k){
//Sort the Array; Time complexity:O(nlogn)
Arrays.sort(a);
// to store the max length of
// array with difference <= k
int max = Integer.MIN_VALUE;
int i=0;
// J goes from 1 to n-1 in n-2 iterations
// Thus time complexity of below loop is O(n)
for(int j=i+1;j<n && i<n;j++){
// if the subarray from i to j index is valid
// the store it's length
if(a[j]-a[i] <= k){
max = Math.max(max, j-i+1);
}
// if subarray difference exceeds k
// change starting position, i.e. i
else{
i++;
}
}
// no. of elements need to be removed is
// Length of array - max subarray with diff <= k
int removed = n-max;
return removed;
}
//Driver Code
public static void main (String[] args) {
int a[] = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = a.length;
int k = 4;
System.out.print(removal(a, n, k));
}
}
Python
# Python program for the above approach def removal(a, n, k): # sort the array a.sort() # to store the max length of # array with difference <= k maxLen = 0 # pointer to keep track of starting of each subarray i = 0 for j in range(i+1, n): # if the subarray from i to j index is valid # the store it's length if a[j]-a[i] <= k: maxLen = max(maxLen, j-i+1) # if subarray difference exceeds k # change starting position, i.e. i else: i = i+1 if i >= n: break remove = n-maxLen return remove # Driver Code a = [1, 3, 4, 9, 10, 11, 12, 17, 20] n = len(a) k = 4 print(removal(a, n, k))
C#
// C# program for the above approach
using System;
class GFG {
static int removal(int[] a, int n, int k)
{
// Sort the Array; Time complexity:O(nlogn)
Array.Sort(a);
// to store the max length of
// array with difference <= k
int max = Int32.MinValue;
int i = 0;
// J goes from 1 to n-1 in n-2 iterations
// Thus time complexity of below loop is O(n)
for (int j = i + 1; j < n && i < n; j++)
{
// if the subarray from i to j index is valid
// the store it's length
if (a[j] - a[i] <= k) {
max = Math.Max(max, j - i + 1);
}
// if subarray difference exceeds k
// change starting position, i.e. i
else {
i++;
}
}
// no. of elements need to be removed is
// Length of array - max subarray with diff <= k
int removed = n - max;
return removed;
}
// Driver Code
public static void Main()
{
int[] a = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = a.Length;
int k = 4;
Console.Write(removal(a, n, k));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for the above approach
function removal(a, n, k)
{
// sort the array
a.sort((a,b)=>a-b)
// to store the max length of
// array with difference <= k
let maxLen = 0;
// pointer to keep track of starting of each subarray
let i = 0;
for(let j = i + 1; j < n; j++)
{
// if the subarray from i to j index is valid
// the store it's length
if(a[j]-a[i] <= k){
maxLen = Math.max(maxLen, j-i+1);
}
// if subarray difference exceeds k
// change starting position, i.e. i
else i++;
if(i >= n)break;
}
let remove = n-maxLen;
return remove;
}
// Driver Code
let a = [1, 3, 4, 9, 10, 11, 12, 17, 20];
let n = a.length;
let k = 4;
document.write(removal(a, n, k),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
5
Complejidad de tiempo: O(nlogn) Para ordenar la array, necesitamos tiempo O(nlogn) y no espacio extra. Y para el cálculo, solo recorremos el ciclo una vez, por lo que tiene una complejidad de tiempo O (n). Entonces, la complejidad del tiempo total es O (nlogn).
Espacio Auxiliar: O(1)
Acercarse:
Aquí estamos aplicando una ventana deslizante, mantendremos a[max]-a[min]<=k. Primero, se debe usar el orden ascendente para ordenar la array. Mantienen dos punteros, llamémoslos I y j, j iterando desde el índice 1 al índice n-1 y haciendo un seguimiento del subarreglo final con la diferencia en max y min menor que k, y yo haciendo un seguimiento del índice inicial del subarreglo Actualizamos la longitud de I a j en una variable para rastrear la longitud máxima hasta el momento si descubrimos que a[j] – a[i]=k (lo que significa que el subarreglo I a j es legítimo). Si no, sumamos i+1 al índice inicial i.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int removal(int a[], int n, int k)
{
// Code here
// Sort the Array; Time complexity:O(nlogn)
sort(a, a + n);
int diff= 0; // to store difference of max(a) and min(a)
int ans = 0; // to store maximum length of array with length <=k
// use sliding window to iterate array, maintaing two
// pointers for desired subarray
// which starting from index j and ending with index i
for (int i = 0, j = 0; i < n; i++) {
int diff = a[i] - a[j];
// as array is already sorted, if difference exceeds
// k we will move starting pointer forward
while (i >= j && diff > k) {
diff = a[i] - a[++j];
}
ans = max(ans, i - j + 1);
}
return n - ans;
}
// Driver Code
int main()
{
int a[] = { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
cout << removal(a, n, k);
return 0;
}
// This code is contributed by Gaurav Garg
Java
// JAVA program for the above approach
import java.util.*;
class GFG {
public static int removal(int[] a, int n, int k)
{
// Code here
// Sort the Array; Time complexity:O(nlogn)
Arrays.sort(a);
int diff
= 0; // to store difference of max(a) and min(a)
int ans = 0; // to store maximum length of array
// with length <=k
// use sliding window to iterate array, maintaing
// two pointers for desired subarray which starting
// from index j and ending with index i
for (int i = 0, j = 0; i < n; i++)
{
diff = a[i] - a[j];
// as array is already sorted, if difference
// exceeds k we will move starting pointer
// forward
while (i >= j && diff > k) {
diff = a[i] - a[++j];
}
ans = Math.max(ans, i - j + 1);
}
return n - ans;
}
// Driver Code
public static void main(String[] args)
{
int a[]
= new int[] { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = a.length;
int k = 4;
System.out.print(removal(a, n, k));
}
}
// This code is contributed by Taranpreet
C#
// C# program for the above approach
using System;
using System.Collections;
public class GFG {
static int removal(int[] a, int n, int k)
{
// Sort the Array
Array.Sort(a);
int diff
= 0; // to store difference of max(a) and min(a)
int ans = 0; // to store maximum length of array
// with length <=k
// use sliding window to iterate array, maintaing
// two pointers for desired subarray which starting
// from index j and ending with index i
for (int i = 0, j = 0; i < n; i++) {
diff = a[i] - a[j];
// as array is already sorted, if difference
// exceeds k we will move starting pointer
// forward
while (i >= j && diff > k) {
diff = a[i] - a[++j];
}
ans = Math.Max(ans, i - j + 1);
}
return n - ans;
}
static public void Main()
{
// Code
int[] a
= new int[] { 1, 3, 4, 9, 10, 11, 12, 17, 20 };
int n = a.Length;
int k = 4;
Console.Write(removal(a, n, k));
}
}
// This code is contributed by lokesh (lokeshmvs21).
Producción
5
Complejidad de tiempo: O(nlogn)
Espacio Auxiliar: O(1)