Given two 2D arrays arr[][] and brr[][] of equal size. The task is to find the minimum number of rotations required either clockwise or anticlockwise to convert arr[][] to brr[][], in the following manner:
- +x means x rotation in clockwise direction
- -x means x rotation in anti-clockwise direction
- 0 means no rotation needed, and
- NA means rotation is not possible
Examples
Input: arr[][] = {{2, 3}, {4, 5}}, brr[][] = {{4, 2}, {5, 3}}
Output: +1
Explanation: arr[][] can be converted to brr[][] by one 90 degree rotation clockwise.Input: arr[][] = {{1, 2}, {3, 4}}, brr[][] = {{1, 3}, {2, 4}}
Output: NA
Approach: The given problem is implementation-based and similar to Rotate matrix with 90 degrees. Follow the steps below to solve the given problem.
- Create a function say rotate(), that rotates a matrix by 90 degrees in the clockwise direction.
- Create a function say isEqual(), to check if two matrices are equal or not.
- At first, check if both the arrays are already equal or not. if equal print 0 and return, as 0 operations are needed in that case.
- Rotate arr[][] by 90 degrees 4 times and each time check whether it became equal to brr or not.
- If at any point arr[][] becomes equal to brr[][] then check if taking clockwise or anti-clockwise is giving the minimum number or rotation to reach brr[][].
- Print the result found above.
- If after 4 clockwise rotations arr[][] never became equal to brr[][] then print NA at the end.
Below is the implementation of the approach:
C++
// C++ program for above approach#include <bits/stdc++.h>#include <vector>using namespace std;// Function to check if two matrices// are equal or notbool isEqual(vector<vector<int> >& arr, vector<vector<int> >& brr){ int n = arr.size(); int m = arr[0].size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] != brr[i][j]) return false; } } return true;}// Function to rotate matrix by 90 degrees clockwisevoid rotate(vector<vector<int> >& m){ int n = m.size(); for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) swap(m[i][j], m[j][i]); for (int i = 0; i < n; i++) reverse(m[i].begin(), m[i].end());}// Find Minimum rotation to reach the desired matrixvoid findRotation(vector<vector<int> > arr, vector<vector<int> > brr){ if (isEqual(arr, brr)) { cout << 0; return; } for (int i = 1; i < 4; i++) { // Rotate by 90 degrees clockwise rotate(arr); // Checking if both arr[][] and brr[] // are now equal or not if (isEqual(arr, brr)) { if (i < 4 - i) { cout << "+" << i; } else cout << "-" << 4 - i; return; } } // If converting brr[][] is not possible cout << "NA";}// Driver Codeint main(){ vector<vector<int> > arr, brr; arr = { { 2, 3 }, { 4, 5 } }; brr = { { 4, 2 }, { 5, 3 } }; // Function Call findRotation(arr, brr); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to check if two matrices // are equal or not static Boolean isEqual(int[ ][ ] arr, int[ ][ ] brr) { int n = arr.length; int m = arr[0].length; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] != brr[i][j]) return false; } } return true; } // Function to rotate matrix by 90 degrees clockwise static void rotate(int [ ][ ] m) { int n = m.length; for (int i = 0; i < n; i++) for (int j = 0; j < i; j++){ //swap int temp = m[i][j]; m[i][j] = m[j][i]; m[j][i] = temp; } for (int i = 0; i < n; i++) Collections.reverse(Arrays.asList(m[i])); } // Find Minimum rotation to reach the desired matrix static void findRotation(int[ ][ ] arr, int[ ][ ] brr) { if (isEqual(arr, brr) == true) { System.out.print("0"); return; } for (int i = 1; i < 4; i++) { // Rotate by 90 degrees clockwise rotate(arr); // Checking if both arr[][] and brr[] // are now equal or not if (!isEqual(arr, brr)) { if (i < 4 - i) { System.out.print("+" + i ); } else System.out.print("-" + (4 - i)); return; } } // If converting brr[][] is not possible System.out.print("NA"); } // Driver Code public static void main (String[] args) { int [ ][ ] arr = { { 2, 3 }, { 4, 5 } }; int [ ][ ] brr = { { 4, 2 }, { 5, 3 } }; // Function Call findRotation(arr, brr); }}// This code is contributed by hrithikgarg03188 |
Python3
# python3 program for above approach# Function to check if two matrices# are equal or notdef isEqual(arr, brr): n = len(arr) m = len(arr[0]) for i in range(0, n): for j in range(0, m): if (arr[i][j] != brr[i][j]): return False return True# Function to rotate matrix by 90 degrees clockwisedef rotate(m): n = len(m) for i in range(0, n): for j in range(0, i): temp = m[i][j] m[i][j] = m[j][i] m[j][i] = temp for i in range(0, n): m[i].reverse()# Find Minimum rotation to reach the desired matrixdef findRotation(arr, brr): if (isEqual(arr, brr)): print(0) return for i in range(1, 4): # Rotate by 90 degrees clockwise rotate(arr) # Checking if both arr[][] and brr[] # are now equal or not if (isEqual(arr, brr)): if (i < 4 - i): print(f"+{i}") else: print(f"-{4-i}") return # If converting brr[][] is not possible print("NA")# Driver Codeif __name__ == "__main__": arr = [[2, 3], [4, 5]] brr = [[4, 2], [5, 3]] # Function Call findRotation(arr, brr) # This code is contributed by rakeshsahni |
C#
using System;using System.Linq;class GFG { static void reverse(int [,]arr, int N, int M) { // Traverse each row of [,]arr for (int i = 0; i < M; i++) { // Initialise start and end index int start = 0; int end = N - 1; // Till start < end, swap the element // at start and end index while (start < end) { // Swap the element int temp = arr[i,start]; arr[i, start] = arr[i, end]; arr[i, end] = temp; // Increment start and decrement // end for next pair of swapping start++; end--; } } } // Function to check if two matrices // are equal or not static bool isEqual(int [,] arr, int [,] brr, int n, int m) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i,j] != brr[i,j]) return false; } } return true; } // Function to rotate matrix by 90 degrees clockwise static void rotate(int [,] arr, int n, int m) { for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) { int curr = arr[i,j]; arr[i,j] = arr[j,i]; arr[j,i] = curr; } reverse(arr,n,m); } // Find Minimum rotation to reach the desired matrix static void findRotation(int [,] arr, int [,] brr, int n, int m) { if (isEqual(arr, brr, n, m)) { Console.Write(0); return; } for (int i = 1; i < 4; i++) { // Rotate by 90 degrees clockwise rotate(arr,n,m); // Checking if both arr[][] and brr[] // are now equal or not if (isEqual(arr, brr,n,m)) { if (i < 4 - i) { Console.Write( "+" + i); } else Console.Write("-" + (4 - i)); return; } } // If converting brr[][] is not possible Console.Write("NA"); } /* Driver program to test above functions */ public static void Main() { int [,] arr = new int[,] { { 2, 3 }, { 4, 5 } }; int [,] brr = new int[,] { { 4, 2 }, { 5, 3 } }; int N = 2; int M = 2; // Function Call findRotation(arr, brr, N, M); }}// This code is contributed by Aarti_Rathi |
Javascript
<script> // JavaScript code for the above approach // Function to check if two matrices // are equal or not function isEqual(arr, brr) { let n = arr.length; let m = arr[0].length; for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (arr[i][j] != brr[i][j]) return false; } } return true; } // Function to rotate matrix by 90 degrees clockwise function rotate(m) { let n = m.length; for (let i = 0; i < n; i++) { for (let j = 0; j < i; j++) { let temp = m[i][j] m[i][j] = m[j][i] m[j][i] = temp } } for (let i = 0; i < n; i++) m[i].reverse() } // Find Minimum rotation to reach the desired matrix function findRotation(arr, brr) { if (isEqual(arr, brr)) { document.write(0) return; } for (let i = 1; i < 4; i++) { // Rotate by 90 degrees clockwise rotate(arr); // Checking if both arr[][] and brr[] // are now equal or not if (isEqual(arr, brr)) { if (i < 4 - i) { document.write("+" + i); } else document.write("-" + (4 - i)); return; } } // If converting brr[][] is not possible document.write("NA"); } // Driver Code let arr, brr; arr = [[2, 3], [4, 5]]; brr = [[4, 2], [5, 3]]; // Function Call findRotation(arr, brr);// This code is contributed by Potta Lokesh </script> |
Output
+1
Time Complexity: O(N*M)
Auxiliary Space: O(1)
Share your thoughts in the comments
