Given two binary matrices, A[][] and B[][] of N×M. In a single operation, one can choose a sub-matrix (min of 2 rows and 2c columns) and change the parity of the corner elements i.e. 1 can be changed to a 0, and 0 can be changed to a 1. The task is to check if matrix A can be converted to B using any number of operations.
Examples:
Input: A[][] = {{0, 1, 0}, {0, 1, 0}, {1, 0, 0}},
B[][] = {{1, 0, 0}, {1, 0, 0}, {1, 0, 0}}
Output: Yes
Choose the sub-matrix whose top-left corner is (0, 0)
and bottom-right corner is (1, 1).
Changing the parity of the corner elements
of this sub-matrix will convert A[][] to B[][]Input: A[][] = {{0, 1, 0, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}},
B[][] = {{1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}}
Output: No
Approach: The first thing to notice is that despite the conversions the total parity of both the matrix will remain the same. Hence, check if a[i][j] is not same as b[i][j] then change the parity of the corner elements of the sub-matrix whose left top corner is (0, 0) and right bottom corner is (i, j) for 1 ? i, j. After performing parity change for every a[i][j] which is not equal to b[i][j], check if both the matrix are the same or not. If they are the same, we can change A to B.
Below is the implementation of the above approach:
C++
// C++ implementation of the// above approach#include <bits/stdc++.h>using namespace std;#define N 3#define M 3// Boolean function that returns// true or falsebool check(int a[N][M], int b[N][M]){ // Traverse for all elements for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If both are not equal if (a[i][j] != b[i][j]) { // Change the parity of // all corner elements a[i][j] ^= 1; a[0][0] ^= 1; a[0][j] ^= 1; a[i][0] ^= 1; } } } // Check if A is equal to B for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // Not equal if (a[i][j] != b[i][j]) return false; } } return true;}// Driver Codeint main(){ // First binary matrix int a[N][N] = { { 0, 1, 0 }, { 0, 1, 0 }, { 1, 0, 0 } }; // Second binary matrix int b[N][N] = { { 1, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 } }; if (check(a, b)) cout << "Yes"; else cout << "No";} |
Java
// Java implementation of the// above approachimport java.io.*;public class GFG { static final int N = 3, M = 3; // Boolean function that returns // true or false static boolean check(int a[][], int b[][]) { // Traverse for all elements for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If both are not equal if (a[i][j] != b[i][j]) { // Change the parity of // all corner elements a[i][j] ^= 1; a[0][0] ^= 1; a[0][j] ^= 1; a[i][0] ^= 1; } } } // Check if A is equal to B for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // Not equal if (a[i][j] != b[i][j]) return false; } } return true; } // Driver Code public static void main(String args[]) { // First binary matrix int a[][] = { { 0, 1, 0 }, { 0, 1, 0 }, { 1, 0, 0 } }; // Second binary matrix int b[][] = { { 1, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 } }; if (check(a, b)) System.out.print("Yes"); else System.out.print("No"); }}// This code is contributed by Arnab Kundu |
Python3
# Python 3 implementation of the# above approachN = 3M = 3# Boolean function that returns# true or falsedef check(a, b): # Traverse for all elements for i in range(1, N, 1): for j in range(1, M, 1): # If both are not equal if (a[i][j] != b[i][j]): # Change the parity of # all corner elements a[i][j] ^= 1 a[0][0] ^= 1 a[0][j] ^= 1 a[i][0] ^= 1 # Check if A is equal to B for i in range(N): for j in range(M): # Not equal if (a[i][j] != b[i][j]): return False return True# Driver Codeif __name__ == '__main__': # First binary matrix a = [[0, 1, 0], [0, 1, 0], [1, 0, 0]] # Second binary matrix b = [[1, 0, 0], [1, 0, 0], [1, 0, 0]] if (check(a, b)): print("Yes") else: print("No")# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the // above approach using System; class GFG{ static readonly int N = 3,M =3; // Boolean function that returns // true or false static bool check(int [,]a, int [,]b) { // Traverse for all elements for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If both are not equal if (a[i,j] != b[i,j]) { // Change the parity of // all corner elements a[i,j] ^= 1; a[0,0] ^= 1; a[0,j] ^= 1; a[i,0] ^= 1; } } } // Check if A is equal to B for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // Not equal if (a[i,j] != b[i,j]) return false; } } return true; } // Driver Code public static void Main(String []args){ // First binary matrix int [,]a = { { 0, 1, 0 }, { 0, 1, 0 }, { 1, 0, 0 } }; // Second binary matrix int [,]b = { { 1, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 } }; if (check(a, b)) Console.Write( "Yes"); else Console.Write( "No"); } }// This code has been contributed by 29AjayKumar |
PHP
<?php// PHP implementation of the above approach $N = 3; $M = 3 ;// Boolean function that returns // true or false function check($a, $b) { // Traverse for all elements for ($i = 1; $i < $GLOBALS['N']; $i++) { for ($j = 1; $j < $GLOBALS['M']; $j++) { // If both are not equal if ($a[$i][$j] != $b[$i][$j]) { // Change the parity of // all corner elements $a[$i][$j] ^= 1; $a[0][0] ^= 1; $a[0][$j] ^= 1; $a[$i][0] ^= 1; } } } // Check if A is equal to B for ($i = 0; $i < $GLOBALS['N']; $i++) { for ($j = 0; $j < $GLOBALS['M']; $j++) { // Not equal if ($a[$i][$j] != $b[$i][$j]) return false; } } return true; } // Driver Code // First binary matrix $a = array(array( 0, 1, 0 ), array( 0, 1, 0 ), array( 1, 0, 0 ) ); // Second binary matrix $b = array( array( 1, 0, 0 ), array(1, 0, 0 ), array( 1, 0, 0 ) ); if (check($a, $b)) echo "Yes"; else echo "No"; // This code is contributed by Ryuga?> |
Javascript
<script>// javascript implementation of the // above approach var N = 3, M = 3; // Boolean function that returns // true or false function check(a , b) { // Traverse for all elements for (i = 1; i < N; i++) { for (j = 1; j < M; j++) { // If both are not equal if (a[i][j] != b[i][j]) { // Change the parity of // all corner elements a[i][j] ^= 1; a[0][0] ^= 1; a[0][j] ^= 1; a[i][0] ^= 1; } } } // Check if A is equal to B for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { // Not equal if (a[i][j] != b[i][j]) return false; } } return true; } // Driver Code // First binary matrix var a = [ [ 0, 1, 0 ], [ 0, 1, 0 ], [ 1, 0, 0 ] ]; // Second binary matrix var b = [ [ 1, 0, 0 ], [ 1, 0, 0 ], [ 1, 0, 0 ] ]; if (check(a, b)) document.write("Yes"); else document.write("No");// This code contributed by aashish1995</script> |
Output
Yes
Time Complexity: O(N * M)
Auxiliary Space: O(1)
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!