Dados dos arreglos de permutación A[] y B[] de los primeros N números naturales , la tarea es encontrar el número mínimo de operaciones requeridas para eliminar todos los elementos del arreglo A[] de modo que en cada operación elimine la subsecuencia de los elementos del arreglo A[ ] cuyo orden es el mismo que en el arreglo B[] .
Ejemplo:
Entrada: A[] = { 4, 2, 1, 3 }, B[] = { 1, 3, 2, 4 }
Salida: 3
Explicación:
El ejemplo dado se puede resolver siguiendo los pasos dados:
- Durante la primera operación, los números enteros en el índice 2 y 3 en la array A[] se pueden eliminar. Por lo tanto, la array A[] = {4, 2}.
- Durante la segunda operación, se puede eliminar el entero en el índice 1 en la array A[]. Por lo tanto, la array A[] = {4}.
- Durante la tercera operación, se puede eliminar el entero en el índice 0 en la array A[]. Por lo tanto, la array A[] = {}.
El orden en el que se eliminan los elementos es {1, 3, 2, 4} que es igual a B. Por lo tanto, se requiere un mínimo de 3 operaciones.
Entrada: A[] = {2, 4, 6, 1, 5, 3}, B[] = {6, 5, 4, 2, 3, 1} Salida
: 4
Enfoque: El problema dado se puede resolver siguiendo los pasos que se describen a continuación:
- Cree dos variables i y j , donde i realiza un seguimiento del índice del elemento actual de B que se eliminará a continuación y j realiza un seguimiento del elemento actual de A . Inicialmente, tanto i=0 como j=0 .
- Atraviese la array de permutación A[] usando j para todos los valores de j en el rango [0, N-1] . Si A[j] = B[i] , incremente el valor de i en 1 y continúe recorriendo la array A[] .
- Después de que la array A[] se haya recorrido por completo, incremente el valor de la variable cnt que mantiene el recuento de las operaciones requeridas.
- Repita los pasos 2 y 3 hasta i<N .
- Después de completar los pasos anteriores, el valor almacenado en cnt es la respuesta requerida.
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 find the minimum number of
// operations to delete all elements of
// permutation A in order described by B
int minOperations(int A[], int B[], int N)
{
// Stores the count of operations
int cnt = 0;
// Stores the index of current integer
// in B to be deleted
int i = 0;
// Loop to iterate over all values of B
while (i < N) {
// Stores the current index in A
int j = 0;
// Iterate over all values A
while (j < N && i < N) {
// If current integer of B and A
// equal, increment the index of
// the current integer of B
if (B[i] == A[j]) {
i++;
}
j++;
}
// As the permutation A has been
// traversed completelly, increment
// the count of operations by 1
cnt++;
}
// Return Answer
return cnt;
}
// Driver Code
int main()
{
int A[] = { 2, 4, 6, 1, 5, 3 };
int B[] = { 6, 5, 4, 2, 3, 1 };
int N = sizeof(A) / sizeof(A[0]);
cout << minOperations(A, B, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum number of
// operations to delete all elements of
// permutation A in order described by B
static int minOperations(int A[], int B[], int N)
{
// Stores the count of operations
int cnt = 0;
// Stores the index of current integer
// in B to be deleted
int i = 0;
// Loop to iterate over all values of B
while (i < N) {
// Stores the current index in A
int j = 0;
// Iterate over all values A
while (j < N && i < N) {
// If current integer of B and A
// equal, increment the index of
// the current integer of B
if (B[i] == A[j]) {
i++;
}
j++;
}
// As the permutation A has been
// traversed completely, increment
// the count of operations by 1
cnt++;
}
// Return Answer
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 2, 4, 6, 1, 5, 3 };
int B[] = { 6, 5, 4, 2, 3, 1 };
int N = A.length;
System.out.print(minOperations(A, B, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach # Function to find the minimum number of # operations to delete all elements of # permutation A in order described by B def minOperations(A, B, N): # Stores the count of operations cnt = 0 # Stores the index of current integer # in B to be deleted i = 0 # Loop to iterate over all values of B while(i < N): # Stores the current index in A j = 0 # Iterate over all values A while (j < N and i < N): # If current integer of B and A # equal, increment the index of # the current integer of B if (B[i] == A[j]): i += 1 j += 1 # As the permutation A has been # traversed completely, increment # the count of operations by 1 cnt += 1 # Return Answer return cnt # Driver Code if __name__ == '__main__': A = [2, 4, 6, 1, 5, 3] B = [6, 5, 4, 2, 3, 1] N = len(A) print(minOperations(A, B, N)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the minimum number of
// operations to delete all elements of
// permutation A in order described by B
static int minOperations(int[] A, int[] B, int N)
{
// Stores the count of operations
int cnt = 0;
// Stores the index of current integer
// in B to be deleted
int i = 0;
// Loop to iterate over all values of B
while (i < N) {
// Stores the current index in A
int j = 0;
// Iterate over all values A
while (j < N && i < N) {
// If current integer of B and A
// equal, increment the index of
// the current integer of B
if (B[i] == A[j]) {
i++;
}
j++;
}
// As the permutation A has been
// traversed completely, increment
// the count of operations by 1
cnt++;
}
// Return Answer
return cnt;
}
// Driver Code
public static void Main(string[] args)
{
int[] A = { 2, 4, 6, 1, 5, 3 };
int[] B = { 6, 5, 4, 2, 3, 1 };
int N = A.Length;
Console.WriteLine(minOperations(A, B, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum number of
// operations to delete all elements of
// permutation A in order described by B
function minOperations(A, B, N) {
// Stores the count of operations
let cnt = 0;
// Stores the index of current integer
// in B to be deleted
let i = 0;
// Loop to iterate over all values of B
while (i < N) {
// Stores the current index in A
let j = 0;
// Iterate over all values A
while (j < N && i < N) {
// If current integer of B and A
// equal, increment the index of
// the current integer of B
if (B[i] == A[j]) {
i++;
}
j++;
}
// As the permutation A has been
// traversed completely, increment
// the count of operations by 1
cnt++;
}
// Return Answer
return cnt;
}
// Driver Code
let A = [2, 4, 6, 1, 5, 3];
let B = [6, 5, 4, 2, 3, 1];
let N = A.length;
document.write(minOperations(A, B, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aniket173000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA