Dados dos arreglos A[] y B[] de longitud N , la tarea es encontrar el número mínimo de operaciones en las que el arreglo A se puede convertir en el arreglo B donde cada operación consiste en agregar un entero K a un subarreglo de L a r
Ejemplos:
Entrada: A[] = {3, 7, 1, 4, 1, 2}, B[] = {3, 7, 3, 6, 3, 2}
Salida: 1
Explicación:
En el ejemplo anterior, solo una operación se requiere para convertir de A a B: L = 3, R = 5 y K = 2
Array después de la siguiente operación:
Índice 0: A[0] = 3, B[0] = 3
Índice 1: A[1] = 7, B[1] = 7
Índice 2: A[2] = 1 + 2 = 3, B[2] = 3
Índice 3: A[3] = 4 + 2 = 6, B[3] = 6
Índice 4 : A[4] = 1 + 2 = 3, B[4] = 3
Índice 5: A[5] = 2, B[5] = 2Entrada: A[] = {1, 1, 1, 1, 1}, B[] = {1, 2, 1, 3, 1}
Salida: 2
Explicación:
En el ejemplo anterior, solo se requiere una operación para convertir de A a B –
Operación 1: Sumar 1 a L = 2 a R = 2
Operación 2: Sumar 2 a L = 4 a R = 4
Enfoque: La idea es contar los elementos consecutivos, en la array A, que tienen una diferencia igual con el elemento correspondiente en la array B.
- Encuentre la diferencia del elemento correspondiente de la array A y B:
Difference = A[i] - B[i]
- Si la diferencia de los elementos correspondientes es igual a 0, continúe buscando el siguiente índice.
- De lo contrario, aumente el índice hasta que la diferencia entre los elementos consecutivos no sea igual a la diferencia anterior de los elementos consecutivos.
- Incremente el conteo en 1, hasta que todos los índices se iteren con la misma diferencia.
- Al final, devuelva el recuento como el número mínimo de operaciones.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the // minimum number of operations in // which the array A can be converted // to another array B #include <bits/stdc++.h> using namespace std; // Function to find the minimum // number of operations in which // array A can be converted to array B void checkArray(int a[], int b[], int n) { int operations = 0; int i = 0; // Loop to iterate over the array while (i < n) { // if both elements are equal // then move to next element if (a[i] - b[i] == 0) { i++; continue; } // Calculate the difference // between two elements int diff = a[i] - b[i]; i++; // loop while the next pair of // elements have same difference while (i < n && a[i] - b[i] == diff) { i++; } // Increase the number of // operations by 1 operations++; } // Print the number of // operations required cout << operations << "\n"; } // Driver Code int main() { int a[] = { 3, 7, 1, 4, 1, 2 }; int b[] = { 3, 7, 3, 6, 3, 2 }; int size = sizeof(a) / sizeof(a[0]); checkArray(a, b, size); return 0; }
Java
// Java implementation to find the // minimum number of operations in // which the array A can be converted // to another array B class GFG { // Function to find the minimum // number of operations in which // array A can be converted to array B static void checkArray(int a[], int b[], int n) { int operations = 0; int i = 0; // Loop to iterate over the array while (i < n) { // if both elements are equal // then move to next element if (a[i] - b[i] == 0) { i++; continue; } // Calculate the difference // between two elements int diff = a[i] - b[i]; i++; // loop while the next pair of // elements have same difference while (i < n && a[i] - b[i] == diff) { i++; } // Increase the number of // operations by 1 operations++; } // Print the number of // operations required System.out.println(operations); } // Driver Code public static void main (String[] args) { int a[] = { 3, 7, 1, 4, 1, 2 }; int b[] = { 3, 7, 3, 6, 3, 2 }; int size = a.length; checkArray(a, b, size); } } // This code is contributed by AnkitRai01
C#
// C# implementation to find the // minimum number of operations in // which the array A can be converted // to another array B using System; class GFG { // Function to find the minimum // number of operations in which // array A can be converted to array B static void checkArray(int []a, int []b, int n) { int operations = 0; int i = 0; // Loop to iterate over the array while (i < n) { // if both elements are equal // then move to next element if (a[i] - b[i] == 0) { i++; continue; } // Calculate the difference // between two elements int diff = a[i] - b[i]; i++; // loop while the next pair of // elements have same difference while (i < n && a[i] - b[i] == diff) { i++; } // Increase the number of // operations by 1 operations++; } // Print the number of // operations required Console.WriteLine(operations); } // Driver Code public static void Main (string[] args) { int []a = { 3, 7, 1, 4, 1, 2 }; int []b = { 3, 7, 3, 6, 3, 2 }; int size = a.Length; checkArray(a, b, size); } } // This code is contributed by AnkitRai01
Python3
# Python3 implementation to find the # minimum number of operations in # which the array A can be converted # to another array B # Function to find the minimum # number of operations in which # array A can be converted to array B def checkArray(a, b, n) : operations = 0; i = 0; # Loop to iterate over the array while (i < n) : # if both elements are equal # then move to next element if (a[i] - b[i] == 0) : i += 1; continue; # Calculate the difference # between two elements diff = a[i] - b[i]; i += 1; # loop while the next pair of # elements have same difference while (i < n and a[i] - b[i] == diff) : i += 1; # Increase the number of # operations by 1 operations += 1; # Print the number of # operations required print(operations); # Driver Code if __name__ == "__main__" : a = [ 3, 7, 1, 4, 1, 2 ]; b = [ 3, 7, 3, 6, 3, 2 ]; size = len(a); checkArray(a, b, size); # This code is contributed by AnkitRai01
Javascript
<script> // javascript implementation to find the // minimum number of operations in // which the array A can be converted // to another array B // Function to find the minimum // number of operations in which // array A can be converted to array B function checkArray(a , b , n) { var operations = 0; var i = 0; // Loop to iterate over the array while (i < n) { // if both elements are equal // then move to next element if (a[i] - b[i] == 0) { i++; continue; } // Calculate the difference // between two elements var diff = a[i] - b[i]; i++; // loop while the next pair of // elements have same difference while (i < n && a[i] - b[i] == diff) { i++; } // Increase the number of // operations by 1 operations++; } // Print the number of // operations required document.write(operations); } // Driver Code var a = [ 3, 7, 1, 4, 1, 2 ]; var b = [ 3, 7, 3, 6, 3, 2 ]; var size = a.length; checkArray(a, b, size); // This code contributed by Rajput-Ji </script>
Análisis de rendimiento:
- Complejidad de tiempo: como en el enfoque anterior, solo hay un ciclo que toma el tiempo O (N) en el peor de los casos. Por lo tanto, la Complejidad del Tiempo será O(N) .
- Complejidad del espacio auxiliar: como en el enfoque anterior, no se utiliza espacio adicional. Por lo tanto, la complejidad del espacio auxiliar será O(1) .
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA