Given a matrix with N rows and M columns, the task is make all possible paths from the cell (N, M) to (1, 1) palindrome by minimum changes in the cell values.
Possible moves from any cell (x, y) is either move Left(x – 1, y) or move Down (x, y – 1).
Examples:
Input: mat[ ][ ] = { { 1, 2, 2 }, { 1, 0, 0 } }
Output: 3
Explanation:
For each path in matrix to be Palindrome, possible matrices (after changes) are
{ { 0, 2, 2 }, { 2, 2, 0 } } or { { 1, 2, 2 }, { 2, 2, 1 } }.
Input: mat[ ][ ] = { { 5, 3 }, { 0, 5 } }
Output: 0
Explanation:
No change required in above matrix. Each path from (N, M) to (1, 1) is already Palindrome
Approach:
- A path is called palindromic if the value of the last cell is equal to the value of the first cell, the value of the second last cell is equal to the value of the second cell, and so on.
- So we can conclude that, to make a path palindromic, the cells at distance (Manhatten distance) x from (N, M) must be equal to the cells at distance x from (1, 1).
- To minimize the number of changes, convert each cell at distance x from (1, 1) and (N, M) to the most frequent among all values present in those cells.
Below is the implementation of the above approach.
C++
// C++ Program to implement the // above approach #include <bits/stdc++.h> using namespace std; #define N 7 // Function for counting changes int countChanges(int matrix[][N], int n, int m) { // Maximum distance possible // is (n - 1 + m - 1) int dist = n + m - 1; // Stores the maximum element int Max_element = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Update the maximum Max_element = max(Max_element, matrix[i][j]); } } // Stores frequencies of // values for respective // distances int freq[dist][Max_element + 1]; // Initialize frequencies of // cells as 0 for (int i = 0; i < dist; i++) { for (int j = 0; j < Max_element + 1; j++) freq[i][j] = 0; } // Count frequencies of cell // values in the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Increment frequency of // value at distance i+j freq[i + j][(matrix[i][j])]++; } } int min_changes_sum = 0; for (int i = 0; i < dist / 2; i++) { // Store the most frequent // value at i-th distance // from (0, 0) and (N - 1, M - 1) int maximum = 0; int total_values = 0; // Calculate max frequency // and total cells at distance i for (int j = 0; j < Max_element + 1; j++) { maximum = max(maximum, freq[i][j] + freq[n + m - 2 - i][j]); total_values += freq[i][j] + freq[n + m - 2 - i][j]; } // Count changes required // to convert all cells // at i-th distance to // most frequent value min_changes_sum += total_values - maximum; } return min_changes_sum; } // Driver Code int main() { int mat[][N] = { { 7, 0, 3, 1, 8, 1, 3 }, { 0, 4, 0, 1, 0, 4, 0 }, { 3, 1, 8, 3, 1, 0, 7 } }; int minChanges = countChanges(mat, 3, 7); cout << minChanges; return 0; } |
Java
// Java program to implement the // above approach import java.util.*; class GFG{ static int N = 7; // Function for counting changes static int countChanges(int matrix[][], int n, int m) { // Maximum distance possible // is (n - 1 + m - 1) int i, j, dist = n + m - 1; // Stores the maximum element int Max_element = 0; for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { // Update the maximum Max_element = Math.max(Max_element, matrix[i][j]); } } // Stores frequencies of // values for respective // distances int freq[][] = new int[dist][Max_element + 1]; // Initialize frequencies of // cells as 0 for(i = 0; i < dist; i++) { for(j = 0; j < Max_element + 1; j++) freq[i][j] = 0; } // Count frequencies of cell // values in the matrix for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { // Increment frequency of // value at distance i+j freq[i + j][(matrix[i][j])]++; } } int min_changes_sum = 0; for(i = 0; i < dist / 2; i++) { // Store the most frequent // value at i-th distance // from (0, 0) and (N - 1, M - 1) int maximum = 0; int total_values = 0; // Calculate max frequency // and total cells at distance i for(j = 0; j < Max_element + 1; 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]; } // Count changes required // to convert all cells // at i-th distance to // most frequent value min_changes_sum += total_values - maximum; } return min_changes_sum; } // Driver Code public static void main (String []args) { int mat[][] = { { 7, 0, 3, 1, 8, 1, 3 }, { 0, 4, 0, 1, 0, 4, 0 }, { 3, 1, 8, 3, 1, 0, 7 } }; int minChanges = countChanges(mat, 3, 7); System.out.print(minChanges); } } // This code is contributed by chitranayal |
Python3
# Python3 program to implement the # above approach # Function for counting changes def countChanges(matrix, n, m): # Maximum distance possible # is (n - 1 + m - 1) dist = n + m - 1 # Stores the maximum element Max_element = 0 for i in range(n): for j in range(m): # Update the maximum Max_element = max(Max_element, matrix[i][j]) # Stores frequencies of # values for respective # distances freq = [[0 for i in range(Max_element + 1)] for j in range(dist)] # Initialize frequencies of # cells as 0 for i in range(dist): for j in range(Max_element + 1): freq[i][j] = 0 # Count frequencies of cell # values in the matrix for i in range(n): for j in range(m): # Increment frequency of # value at distance i+j freq[i + j][(matrix[i][j])] += 1 min_changes_sum = 0 for i in range(dist // 2): # Store the most frequent # value at i-th distance # from (0, 0) and (N - 1, M - 1) maximum = 0 total_values = 0 # Calculate max frequency # and total cells at distance i for j in range(Max_element + 1): maximum = max(maximum, freq[i][j] + freq[n + m - 2 - i][j]) total_values += (freq[i][j] + freq[n + m - 2 - i][j]) # Count changes required # to convert all cells # at i-th distance to # most frequent value min_changes_sum += total_values - maximum return min_changes_sum # Driver code if __name__ == '__main__': mat = [ [ 7, 0, 3, 1, 8, 1, 3 ], [ 0, 4, 0, 1, 0, 4, 0 ], [ 3, 1, 8, 3, 1, 0, 7 ] ] minChanges = countChanges(mat, 3, 7) print(minChanges) # This code is contributed by Shivam Singh |
C#
// C# program to implement the // above approach using System; class GFG{ //static int N = 7; // Function for counting changes static int countChanges(int [,]matrix, int n, int m) { // Maximum distance possible // is (n - 1 + m - 1) int i, j, dist = n + m - 1; // Stores the maximum element int Max_element = 0; for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { // Update the maximum Max_element = Math.Max(Max_element, matrix[i, j]); } } // Stores frequencies of // values for respective // distances int [,]freq = new int[dist, Max_element + 1]; // Initialize frequencies of // cells as 0 for(i = 0; i < dist; i++) { for(j = 0; j < Max_element + 1; j++) freq[i, j] = 0; } // Count frequencies of cell // values in the matrix for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { // Increment frequency of // value at distance i+j freq[i + j, matrix[i, j]]++; } } int min_changes_sum = 0; for(i = 0; i < dist / 2; i++) { // Store the most frequent // value at i-th distance // from (0, 0) and (N - 1, M - 1) int maximum = 0; int total_values = 0; // Calculate max frequency // and total cells at distance i for(j = 0; j < Max_element + 1; 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]; } // Count changes required // to convert all cells // at i-th distance to // most frequent value min_changes_sum += total_values - maximum; } return min_changes_sum; } // Driver Code public static void Main(String []args) { int [,]mat = { { 7, 0, 3, 1, 8, 1, 3 }, { 0, 4, 0, 1, 0, 4, 0 }, { 3, 1, 8, 3, 1, 0, 7 } }; int minChanges = countChanges(mat, 3, 7); Console.Write(minChanges); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // javascript program to implement // the above approach // Function for counting changes function countChanges(matrix, n, m) { // Maximum distance possible // is (n - 1 + m - 1) let i, j, dist = n + m - 1; // Stores the maximum element let Max_element = 0; for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { // Update the maximum Max_element = Math.max(Max_element, matrix[i][j]); } } // Stores frequencies of // values for respective // distances let freq = new Array(dist); for (i = 0; i < freq.length; i++) { freq[i] = new Array(2); } // Initialize frequencies of // cells as 0 for(i = 0; i < dist; i++) { for(j = 0; j < Max_element + 1; j++) freq[i][j] = 0; } // Count frequencies of cell // values in the matrix for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { // Increment frequency of // value at distance i+j freq[i + j][(matrix[i][j])]++; } } let min_changes_sum = 0; for(i = 0; i <Math.floor(dist / 2); i++) { // Store the most frequent // value at i-th distance // from (0, 0) and (N - 1, M - 1) let maximum = 0; let total_values = 0; // Calculate max frequency // and total cells at distance i for(j = 0; j < Max_element + 1; 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]; } // Count changes required // to convert all cells // at i-th distance to // most frequent value min_changes_sum += total_values - maximum; } return min_changes_sum; } // Driver Code let mat = [[ 7, 0, 3, 1, 8, 1, 3 ], [ 0, 4, 0, 1, 0, 4, 0 ], [ 3, 1, 8, 3, 1, 0, 7 ]]; let minChanges = countChanges(mat, 3, 7); document.write(minChanges); // This code is contributed by avijitmondal1998. </script> |
Output:
6
Time Complexity: O(N * M)
Auxiliary Space: O((N + M)*maxm), where maxm is the maximum element present in the matrix.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
