Given a binary matrix Mat[][] of size N*N, the task is to find the minimum number of flips to be performed such that the matrix is identical for all rotations.
Examples:
Input: Mat[][] = {{1, 0, 0}, {0, 1, 0}, {1, 0, 1}}
Output: 1
Explanation: Change the element at row = 1, col = 3 from 0 to 1.
Now for all the rotations the matrix is identical.Input: {{0}}
Output: 0
Approach: To solve the problem follow the below idea:
Rotate the matrix 4 times and for every position check how many of elements needs to be changed based on their positions in each rotation.
Follow the steps mentioned below to implement the observation:
- Initialize a matrix of size N2 with 0 to store the count of 1 at that position for every rotation.
- Rotate the matrix 4 times and count 1 for every position of the matrix.
- Initialize Sum = 0 and count min(count of 1, count of 0) for every position of Mat[][].
- Return Sum/4, as we count the same position 4 times.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// After transpose we swap// elements of column// one by one for finding left// rotation of matrix// by 90 degreevoid reverseColumns(vector<vector<bool> >& arr){ int R = arr.size(); int C = arr[0].size(); for (int i = 0; i < C; i++) for (int j = 0, k = C - 1; j < k; j++, k--) swap(arr[j][i], arr[k][i]);}// Function to do transpose of matrixvoid transpose(vector<vector<bool> >& arr){ int R = arr.size(); int C = arr[0].size(); for (int i = 0; i < R; i++) for (int j = i; j < C; j++) swap(arr[i][j], arr[j][i]);}// Function to rotate matrix// anticlockwise by 90 degreevoid rotate(vector<vector<bool> >& arr){ transpose(arr); reverseColumns(arr);}// Function to return the minimum number of flipsint solve(vector<vector<bool> > v, int n){ int Sum = 0; // Initialize Count vector vector<vector<int> > c(n, vector<int>(n, 0)); // Count 1 in each position for every rotation for (int t = 0; t < 4; t++) { rotate(v); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (v[i][j] == 1) c[i][j]++; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Sum += min(c[i][j], 4 - c[i][j]); } } // Count Minimum reversal return Sum / 4;}// Driver Codeint main(){ vector<vector<bool> > v = { { 1, 0, 0 }, { 0, 1, 0 }, { 1, 0, 1 } }; int N = 3; // Function call cout << solve(v, N) << endl; return 0;} |
Java
// Java code to implement the above approachimport java.util.*;class GFG { // After transpose we swap // elements of column // one by one for finding left // rotation of matrix // by 90 degree static void reverseColumns(int[][] arr) { int R = arr.length; int C = arr[0].length; for (int i = 0; i < C; i++){ for (int j = 0, k = C - 1; j < k; j++, k--){ int temp = arr[j][i]; arr[j][i] = arr[k][i]; arr[k][i] = temp; } } } // Function to do transpose of matrix static void transpose(int[][] arr) { int R = arr.length; int C = arr[0].length; for (int i = 0; i < R; i++){ for (int j = i; j < C; j++){ int temp = arr[j][i]; arr[j][i] = arr[i][j]; arr[i][j] = temp; } } } // Function to rotate matrix // anticlockwise by 90 degree static void rotate(int[][] arr) { transpose(arr); reverseColumns(arr); } // Function to return the minimum number of flips static int solve(int[][] v, int n) { double Sum = 0.0; // Initialize Count vector int[][] c = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { c[i][j] = 1; } } // Count 1 in each position for every rotation for (int t = 0; t < 4; t++) { rotate(v); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (v[i][j] == 1) c[i][j]++; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Sum += Math.min(c[i][j], 4 - c[i][j]); } } // Count Minimum reversal return (int)Math.round(Sum / 4); } // Driver Code public static void main (String[] args) { int[][] v = { { 1, 0, 0 }, { 0, 1, 0 }, { 1, 0, 1 } }; int N = 3; // Function call System.out.println(solve(v, N)); }}// This code is contributed by sanjoy_62. |
Python3
class GFG : # After transpose we swap # elements of column # one by one for finding left # rotation of matrix # by 90 degree @staticmethod def reverseColumns( arr) : R = len(arr) C = len(arr[0]) i = 0 while (i < C) : j = 0 k = C - 1 while (j < k) : temp = arr[j][i] arr[j][i] = arr[k][i] arr[k][i] = temp j += 1 k -= 1 i += 1 # Function to do transpose of matrix @staticmethod def transpose( arr) : R = len(arr) C = len(arr[0]) i = 0 while (i < R) : j = i while (j < C) : temp = arr[j][i] arr[j][i] = arr[i][j] arr[i][j] = temp j += 1 i += 1 # Function to rotate matrix # anticlockwise by 90 degree @staticmethod def rotate( arr) : GFG.transpose(arr) GFG.reverseColumns(arr) # Function to return the minimum number of flips @staticmethod def solve( v, n) : Sum = 0.0 # Initialize Count vector c = [[0] * (n) for _ in range(n)] i = 0 while (i < n) : j = 0 while (j < n) : c[i][j] = 1 j += 1 i += 1 # Count 1 in each position for every rotation t = 0 while (t < 4) : GFG.rotate(v) i = 0 while (i < n) : j = 0 while (j < n) : if (v[i][j] == 1) : c[i][j] += 1 j += 1 i += 1 t += 1 i = 0 while (i < n) : j = 0 while (j < n) : Sum += min(c[i][j],4 - c[i][j]) j += 1 i += 1 # Count Minimum reversal return int(round(Sum / 4)) # Driver Code @staticmethod def main( args) : v = [[1, 0, 0], [0, 1, 0], [1, 0, 1]] N = 3 # Function call print(GFG.solve(v, N)) if __name__=="__main__": GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# code to implement the above approachusing System;public class GFG{ // After transpose we swap // elements of column // one by one for finding left // rotation of matrix // by 90 degree static void reverseColumns(int[,] arr) { int C = arr.GetLength(1); for (int i = 0; i < C; i++){ for (int j = 0, k = C - 1; j < k; j++, k--){ int temp = arr[j ,i]; arr[j, i] = arr[k ,i]; arr[k, i] = temp; } } } // Function to do transpose of matrix static void transpose(int[, ] arr) { int R = arr.GetLength(0); int C = arr.GetLength(1); for (int i = 0; i < R; i++){ for (int j = i; j < C; j++){ int temp = arr[j,i]; arr[j,i] = arr[i,j]; arr[i,j] = temp; } } } // Function to rotate matrix // anticlockwise by 90 degree static void rotate(int[,] arr) { transpose(arr); reverseColumns(arr); } // Function to return the minimum number of flips static int solve(int[,] v, int n) { double Sum = 0.0; // Initialize Count vector int[,] c = new int[n,n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { c[i,j] = 1; } } // Count 1 in each position for every rotation for (int t = 0; t < 4; t++) { rotate(v); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (v[i,j] == 1) c[i,j]++; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Sum += Math.Min(c[i,j], 4 - c[i,j]); } } // Count Minimum reversal return (int)Math.Round(Sum / 4); } // Driver Code static public void Main (){ int[,] v = new int[,] { { 1, 0, 0 }, { 0, 1, 0 }, { 1, 0, 1 } }; int N = 3; // Function call Console.Write(solve(v, N)); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code for the above approach: // After transpose we swap // elements of column // one by one for finding left // rotation of matrix // by 90 degree const reverseColumns = (arr) => { let R = arr.length; let C = arr[0].length; for (let i = 0; i < C; i++) for (let j = 0, k = C - 1; j < k; j++, k--) { let temp = arr[j][i]; arr[j][i] = arr[k][i]; arr[k][i] = temp; } } // Function to do transpose of matrix const transpose = (arr) => { let R = arr.length; let C = arr[0].length; for (let i = 0; i < R; i++) for (let j = i; j < C; j++) { let temp = arr[j][i]; arr[j][i] = arr[i][j]; arr[i][j] = temp; } } // Function to rotate matrix // anticlockwise by 90 degree const rotate = (arr) => { transpose(arr); reverseColumns(arr); } // Function to return the minimum number of flips const solve = (v, n) => { let Sum = 0; // Initialize Count vector let c = new Array(n).fill(0).map(() => new Array(n).fill(0)); // Count 1 in each position for every rotation for (let t = 0; t < 4; t++) { rotate(v); for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (v[i][j] == 1) c[i][j]++; } } } for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { Sum += Math.min(c[i][j], 4 - c[i][j]); } } // Count Minimum reversal return parseInt(Sum / 4); } // Driver Code let v = [[1, 0, 0], [0, 1, 0], [1, 0, 1]]; let N = 3; // Function call document.write(solve(v, N));// This code is contributed by rakeshsahni</script> |
Output
1
Time Complexity: O(N2)
Auxiliary Space: O(N2)
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!
