Dada una array arr[] (indexación basada en 1) que consta de N enteros y un entero positivo K , la tarea es encontrar la cantidad mínima de elementos de la array que deben eliminarse de modo que al menos K elementos de la array sean iguales a sus valores de índice . Si no es posible hacerlo, imprima -1 .
Ejemplos:
Entrada: arr[] = {5, 1, 3, 2, 3} K = 2
Salida: 2
Explicación: Las
siguientes son las operaciones de eliminación requeridas:
- Eliminar arr[1] modifica la array a {1, 3, 2, 3} -> 1 elemento es igual a su valor de índice.
- Eliminar arr[3] modifica la array a {1, 2, 3} -> 3 elementos son iguales a su valor de índice.
Después de las operaciones anteriores, 3 (> = K) elementos son iguales a sus valores de índice y las eliminaciones mínimas requeridas son 2.
Entrada: arr[] = {2, 3, 4} K = 1
Salida: -1
Enfoque: el problema anterior se puede resolver con la ayuda de la programación dinámica . Siga los pasos a continuación para resolver el problema dado.
- Inicialice una tabla dp 2-D tal que dp[i][j] indicará el máximo de elementos que tienen valores iguales a sus índices cuando hay un total de j elementos presentes.
- Todos los valores de la tabla dp se rellenan inicialmente con ceros .
- Iterar para cada i en el rango [0, N-1 ] y j en el rango [0, i] , hay dos opciones.
- Elimine el elemento actual, la tabla dp se puede actualizar como dp[i+1][j] = max(dp[i+1][j], dp[i][j]) .
- Mantenga el elemento actual, luego la tabla dp se puede actualizar como: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + (arr[ i+1] == j+1)) .
- Ahora, para cada j en el rango [N, 0], compruebe si el valor de dp[N][j] es mayor o igual que K . Tome el mínimo si lo encuentra y devuelva la respuesta.
- De lo contrario, devuelve -1 al final. Eso significa que no se encuentra ninguna respuesta posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to minimize the removals of
// array elements such that atleast K
// elements are equal to their indices
int MinimumRemovals(int a[], int N, int K)
{
// Store the array as 1-based indexing
// Copy of first array
int b[N + 1];
for (int i = 0; i < N; i++) {
b[i + 1] = a[i];
}
// Make a dp-table of (N*N) size
int dp[N + 1][N + 1];
// Fill the dp-table with zeroes
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
// Delete the current element
dp[i + 1][j] = max(
dp[i + 1][j], dp[i][j]);
// Take the current element
dp[i + 1][j + 1] = max(
dp[i + 1][j + 1],
dp[i][j] + ((b[i + 1] == j + 1) ? 1 : 0));
}
}
// Check for the minimum removals
for (int j = N; j >= 0; j--) {
if (dp[N][j] >= K) {
return (N - j);
}
}
return -1;
}
// Driver Code
int main()
{
int arr[] = { 5, 1, 3, 2, 3 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
cout << MinimumRemovals(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to minimize the removals of
// array elements such that atleast K
// elements are equal to their indices
static int MinimumRemovals(int a[], int N, int K)
{
// Store the array as 1-based indexing
// Copy of first array
int b[] = new int[N + 1];
for (int i = 0; i < N; i++) {
b[i + 1] = a[i];
}
// Make a dp-table of (N*N) size
int dp[][] = new int[N + 1][N + 1];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
// Delete the current element
dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);
// Take the current element
dp[i + 1][j + 1] = Math.max(
dp[i + 1][j + 1],
dp[i][j]
+ ((b[i + 1] == j + 1) ? 1 : 0));
}
}
// Check for the minimum removals
for (int j = N; j >= 0; j--) {
if (dp[N][j] >= K) {
return (N - j);
}
}
return -1;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 1, 3, 2, 3 };
int K = 2;
int N = arr.length;
System.out.println(MinimumRemovals(arr, N, K));
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python 3 program for the above approach # Function to minimize the removals of # array elements such that atleast K # elements are equal to their indices def MinimumRemovals(a, N, K): # Store the array as 1-based indexing # Copy of first array b = [0 for i in range(N + 1)] for i in range(N): b[i + 1] = a[i] # Make a dp-table of (N*N) size dp = [[0 for i in range(N+1)] for j in range(N+1)] for i in range(N): for j in range(i + 1): # Delete the current element dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]) # Take the current element dp[i + 1][j + 1] = max(dp[i + 1][j + 1],dp[i][j] + (1 if (b[i + 1] == j + 1) else 0)) # Check for the minimum removals j = N while(j >= 0): if(dp[N][j] >= K): return (N - j) j -= 1 return -1 # Driver Code if __name__ == '__main__': arr = [5, 1, 3, 2, 3] K = 2 N = len(arr) print(MinimumRemovals(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# code for the above approach
using System;
public class GFG
{
// Function to minimize the removals of
// array elements such that atleast K
// elements are equal to their indices
static int MinimumRemovals(int[] a, int N, int K)
{
// Store the array as 1-based indexing
// Copy of first array
int[] b = new int[N + 1];
for (int i = 0; i < N; i++) {
b[i + 1] = a[i];
}
// Make a dp-table of (N*N) size
int[, ] dp = new int[N + 1, N + 1];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
// Delete the current element
dp[i + 1, j]
= Math.Max(dp[i + 1, j], dp[i, j]);
// Take the current element
dp[i + 1, j + 1] = Math.Max(
dp[i + 1, j + 1],
dp[i, j]
+ ((b[i + 1] == j + 1) ? 1 : 0));
}
}
// Check for the minimum removals
for (int j = N; j >= 0; j--) {
if (dp[N, j] >= K) {
return (N - j);
}
}
return -1;
}
static public void Main()
{
// Code
int[] arr = { 5, 1, 3, 2, 3 };
int K = 2;
int N = arr.Length;
Console.Write(MinimumRemovals(arr, N, K));
}
}
// This code is contributed by Potta Lokesh
Javascript
<script>
// Javascript program for the above approach
// Function to minimize the removals of
// array elements such that atleast K
// elements are equal to their indices
function MinimumRemovals(a, N, K)
{
// Store the array as 1-based indexing
// Copy of first array
let b = new Array(N + 1);
for (let i = 0; i < N; i++) {
b[i + 1] = a[i];
}
// Make a dp-table of (N*N) size
let dp = new Array(N + 1).fill(0).map(() => new Array(N + 1).fill(0));
for (let i = 0; i < N; i++) {
for (let j = 0; j <= i; j++) {
// Delete the current element
dp[i + 1][j] = Math.max(
dp[i + 1][j], dp[i][j]);
// Take the current element
dp[i + 1][j + 1] = Math.max(
dp[i + 1][j + 1],
dp[i][j] + ((b[i + 1] == j + 1) ? 1 : 0));
}
}
// Check for the minimum removals
for (let j = N; j >= 0; j--) {
if (dp[N][j] >= K) {
return (N - j);
}
}
return -1;
}
// Driver Code
let arr = [ 5, 1, 3, 2, 3 ];
let K = 2;
let N = arr.length
document.write(MinimumRemovals(arr, N, K));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA