Dada una array mat[][] con N filas y M columnas. La tarea es encontrar el número mínimo de cambios requeridos en la array de modo que cada camino desde la parte superior izquierda hasta la parte inferior derecha sea un camino palindrómico. En un camino, solo se permiten movimientos hacia la derecha y hacia abajo de una celda a otra celda.
Ejemplos:
Entrada: mat[][] = {{1, 2}, {3, 1}}
Salida: 0
Explicación:
Cada camino en la array de arriba a la izquierda a abajo a la derecha es palindrómico.
Rutas => {1, 2, 1}, {1, 3, 1}Entrada: mat[][] = {{1, 2}, {3, 5}}
Salida: 1
Explicación:
Solo se requiere un cambio para que cada ruta sea palindrómica.
Eso es => mat[1][1] = 1
Caminos => {1, 2, 1}, {1, 3, 1}
Enfoque ingenuo: para el enfoque ingenuo, consulte esta publicación.
Enfoque Eficiente: La idea es descartar el uso de un espacio extra que es el uso de HashMap . Siga los pasos que se indican a continuación:
- La distancia posible desde la parte superior izquierda y la parte inferior derecha están en el rango de 0 a N + M – 2 . Por lo tanto, cree una array 2D de dimensiones [N + M – 1][10] .
- Almacene la frecuencia de las distancias en una array mientras considera el número de fila (en el rango de 0 a N + M – 2) como distancia y el número de columna (0 a 9) como un elemento en la array dada.
- Para que el número de cambios sea mínimo , cambie cada celda en la distancia X con un valor que tenga la frecuencia más alta entre todos los valores en la distancia X.
- El número mínimo de pasos necesarios es la suma de la diferencia de los valores totales de frecuencia y el valor máximo de frecuencia para cada distancia.
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; #define N 7 // Function for counting minimum // number of changes int countChanges(int matrix[][N], int n, int m) { // Distance of elements from (0, 0) // will is i range [0, n + m - 2] int dist = n + m - 1; // Store frequencies of [0, 9] // at distance i int freq[dist][10]; // Initialize frequencies as 0 for (int i = 0; i < dist; i++) { for (int j = 0; j < 10; j++) freq[i][j] = 0; } // Count frequencies of [0, 9] for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Increment frequency of // value matrix[i][j] // at distance i+j freq[i + j][matrix[i][j]]++; } } int min_changes_sum = 0; for (int i = 0; i < dist / 2; i++) { int maximum = 0; int total_values = 0; // Find value with max frequency // and count total cells at distance i // from front end and rear end for (int j = 0; j < 10; j++) { maximum = max(maximum, freq[i][j] + freq[n + m - 2 - i][j]); total_values += (freq[i][j] + freq[n + m - 2 - i][j]); } // Change all values to the // value with max frequency min_changes_sum += (total_values - maximum); } // Return the answer return min_changes_sum; } // Driver Code int main() { // Given Matrix int mat[][N] = { { 1, 2 }, { 3, 5 } }; // Function Call cout << countChanges(mat, 2, 2); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ static final int N = 7; // Function for counting minimum // number of changes static int countChanges(int matrix[][], int n, int m) { // Distance of elements from (0, 0) // will is i range [0, n + m - 2] int dist = n + m - 1; // Store frequencies of [0, 9] // at distance i int [][]freq = new int[dist][10]; // Initialize frequencies as 0 for(int i = 0; i < dist; i++) { for(int j = 0; j < 10; j++) freq[i][j] = 0; } // Count frequencies of [0, 9] for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // Increment frequency of // value matrix[i][j] // at distance i+j freq[i + j][matrix[i][j]]++; } } int min_changes_sum = 0; for(int i = 0; i < dist / 2; i++) { int maximum = 0; int total_values = 0; // Find value with max frequency // and count total cells at distance i // from front end and rear end for(int j = 0; j < 10; j++) { maximum = Math.max(maximum, freq[i][j] + freq[n + m - 2 - i][j]); total_values += (freq[i][j] + freq[n + m - 2 - i][j]); } // Change all values to the // value with max frequency min_changes_sum += (total_values - maximum); } // Return the answer return min_changes_sum; } // Driver Code public static void main(String[] args) { // Given matrix int mat[][] = { { 1, 2 }, { 3, 5 } }; // Function call System.out.print(countChanges(mat, 2, 2)); } } // This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach # Function for counting minimum # number of changes def countChanges(matrix, n, m): # Distance of elements from (0, 0) # will is i range [0, n + m - 2] dist = n + m - 1 # Store frequencies of [0, 9] # at distance i # Initialize all with zero freq = [[0] * 10 for i in range(dist)] # Count frequencies of [0, 9] for i in range(n): for j in range(m): # Increment frequency of # value matrix[i][j] # at distance i+j freq[i + j][matrix[i][j]] += 1 min_changes_sum = 0 for i in range(dist // 2): maximum = 0 total_values = 0 # Find value with max frequency # and count total cells at distance i # from front end and rear end for j in range(10): maximum = max(maximum, freq[i][j] + freq[n + m - 2 - i][j]) total_values += (freq[i][j] + freq[n + m - 2 - i][j]) # Change all values to the value # with max frequency min_changes_sum += (total_values - maximum) # Return the answer return min_changes_sum # Driver code if __name__ == '__main__': # Given matrix mat = [ [ 1, 2 ], [ 3, 5 ] ] # Function call print(countChanges(mat, 2, 2)) # This code is contributed by himanshu77
C#
// C# program for the above approach using System; class GFG{ //static readonly int N = 7; // Function for counting minimum // number of changes static int countChanges(int [,]matrix, int n, int m) { // Distance of elements from (0, 0) // will is i range [0, n + m - 2] int dist = n + m - 1; // Store frequencies of [0, 9] // at distance i int [,]freq = new int[dist, 10]; // Initialize frequencies as 0 for(int i = 0; i < dist; i++) { for(int j = 0; j < 10; j++) freq[i, j] = 0; } // Count frequencies of [0, 9] for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // Increment frequency of // value matrix[i,j] // at distance i+j freq[i + j, matrix[i, j]]++; } } int min_changes_sum = 0; for(int i = 0; i < dist / 2; i++) { int maximum = 0; int total_values = 0; // Find value with max frequency // and count total cells at distance i // from front end and rear end for(int j = 0; j < 10; j++) { maximum = Math.Max(maximum, freq[i, j] + freq[n + m - 2 - i, j]); total_values += (freq[i, j] + freq[n + m - 2 - i, j]); } // Change all values to the // value with max frequency min_changes_sum += (total_values - maximum); } // Return the answer return min_changes_sum; } // Driver Code public static void Main(String[] args) { // Given matrix int [,]mat = { { 1, 2 }, { 3, 5 } }; // Function call Console.Write(countChanges(mat, 2, 2)); } } // This code is contributed by Rohit_ranjan
Javascript
<script> // JavaScript program for the above approach var N = 7; // Function for counting minimum // number of changes function countChanges(matrix, n, m) { // Distance of elements from (0, 0) // will is i range [0, n + m - 2] var dist = n + m - 1; // Store frequencies of [0, 9] // at distance i var freq = Array.from(Array(dist), ()=>Array(10)); // Initialize frequencies as 0 for (var i = 0; i < dist; i++) { for (var j = 0; j < 10; j++) freq[i][j] = 0; } // Count frequencies of [0, 9] for (var i = 0; i < n; i++) { for (var j = 0; j < m; j++) { // Increment frequency of // value matrix[i][j] // at distance i+j freq[i + j][matrix[i][j]]++; } } var min_changes_sum = 0; for (var i = 0; i < parseInt(dist / 2); i++) { var maximum = 0; var total_values = 0; // Find value with max frequency // and count total cells at distance i // from front end and rear end for (var j = 0; j < 10; j++) { maximum = Math.max(maximum, freq[i][j] + freq[n + m - 2 - i][j]); total_values += (freq[i][j] + freq[n + m - 2 - i][j]); } // Change all values to the // value with max frequency min_changes_sum += (total_values - maximum); } // Return the answer return min_changes_sum; } // Driver Code // Given Matrix var mat = [[1, 2], [3, 5 ]]; // Function Call document.write( countChanges(mat, 2, 2)); </script>
1
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por himanshu77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA