Given a binary matrix M[][] of dimensions N x N, the task is to make every pair of adjacent cells in the same row or column of the given matrix distinct by swapping the minimum number of rows or columns.
Examples
Input: M[][] = {{0, 1, 1, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}}, N = 4
Output: 2
Explanation:
Step 1: Swapping the 2nd and 3rd rows modifies matrix to the following representation:
M[][] = { { 0, 1, 1, 0},
{ 1, 0, 0, 1},
{ 0, 1, 1, 0},
{ 1, 0, 0, 1} }
Step 1: Swapping the 1st and 2nd columns modifies matrix to the following representation:
M[][] = { { 1, 0, 1, 0},
{ 0, 1, 0, 1},
{ 1, 0, 1, 0},
{ 0, 1, 0, 1} }Input: M[][] = {{0, 1, 1}, {1, 1, 0}, {1, 0, 0}, {1, 1, 1}}, N = 3
Output: -1
Approach: The given problem can be solved based on the following observations:
- In the desired matrix, any submatrix starting from a corner must have Bitwise XOR of all cells equal to 0.
- It can also be observed that there should be at most two types of sequences that should be present in a row or column, i.e. {0, 1, 0, 1} and {1, 0, 1, 1}. Therefore, one sequence can be generated from the other by swapping with the XOR value of that sequence with 1.
- Therefore, by making only the first column and first row according to the required format, the total swaps required will be minimized.
Follow the steps below to solve the problem:
- Traverse in the matrix M[][] and check if bitwise xor of all elements M[i][0], M[0][j], M[0][0], and M[i][j] is 1 then return -1.
- Initialize variables rowSum, colSum, rowSwap, and colSwap with 0.
- Traverse in the range [0, N-1] and increment rowSum by M[i][0], colSum by M[0][i] and increment rowSwap by 1 if M[i][0] is equal to i%2 and colSwap by 1 if M[0][i] is equal to i%2.
- If rowSum is not equal to either of N/2 or (N+1)/2 then return -1.
- If colSum is not equal to either of N/2 or (N+1)/2 then return -1.
- Assign colSwap = N – colSwap if, N%2 and colSwap%2 both are not equal to 0 and rowSwap = N – rowSwap if, N%2 and rowSwap%2 both are not equal to 0.
- Assign colSwap equal to the minimum of colSwap and N-colSwap, and rowSwap equal to the minimum of rowSwap and N-rowSwap.
- Finally, print the result as (rowSum+colSum)/2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return number of moves// to convert matrix into chessboardint minSwaps(vector<vector<int> >& b){ // Size of the matrix int n = b.size(); // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) return -1; } } // Initialize rowSum to count 1s in row int rowSum = 0; // Initialize colSum to count 1s in column int colSum = 0; // To store no. of rows to be corrected int rowSwap = 0; // To store no. of columns to be corrected int colSwap = 0; // Traverse in the range [0, N-1] for (int i = 0; i < n; i++) { rowSum += b[i][0]; colSum += b[0][i]; rowSwap += b[i][0] == i % 2; colSwap += b[0][i] == i % 2; } // Check if rows is either N/2 or // (N+1)/2 and return -1 if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1; // Check if rows is either N/2 // or (N+1)/2 and return -1 if (colSum != n / 2 && colSum != (n + 1) / 2) return -1; // Check if N is odd if (n % 2 == 1) { // Check if column required to be // corrected is odd and then // assign N-colSwap to colSwap if (colSwap % 2) colSwap = n - colSwap; // Check if rows required to // be corrected is odd and then // assign N-rowSwap to rowSwap if (rowSwap % 2) rowSwap = n - rowSwap; } else { // Take min of colSwap and N-colSwap colSwap = min(colSwap, n - colSwap); // Take min of rowSwap and N-rowSwap rowSwap = min(rowSwap, n - rowSwap); } // Finally return answer return (rowSwap + colSwap) / 2;}// Driver Codeint main(){ // Given matrix vector<vector<int> > M = { { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function Call int ans = minSwaps(M); // Print answer cout << ans;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*; class GFG { // Function to return number of moves // to convert matrix into chessboard public static int minSwaps(int[][] b) { // Size of the matrix int n = b.length; // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) == 1) { return -1; } } } // Initialize rowSum to count 1s in row int rowSum = 0; // Initialize colSum to count 1s in column int colSum = 0; // To store no. of rows to be corrected int rowSwap = 0; // To store no. of columns to be corrected int colSwap = 0; // Traverse in the range [0, N-1] for (int i = 0; i < n; i++) { rowSum += b[i][0]; colSum += b[0][i]; int cond1 = 0; int cond2 = 0; if(b[i][0] == i % 2) cond1 = 1; if(b[0][i] == i % 2) cond2 = 1; rowSwap += cond1; colSwap += cond2; } // Check if rows is either N/2 or // (N+1)/2 and return -1 if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1; // Check if rows is either N/2 // or (N+1)/2 and return -1 if (colSum != n / 2 && colSum != (n + 1) / 2) return -1; // Check if N is odd if (n % 2 == 1) { // Check if column required to be // corrected is odd and then // assign N-colSwap to colSwap if ((colSwap % 2) == 1) colSwap = n - colSwap; // Check if rows required to // be corrected is odd and then // assign N-rowSwap to rowSwap if ((rowSwap % 2) == 1) rowSwap = n - rowSwap; } else { // Take min of colSwap and N-colSwap colSwap = Math.min(colSwap, n - colSwap); // Take min of rowSwap and N-rowSwap rowSwap = Math.min(rowSwap, n - rowSwap); } // Finally return answer return (rowSwap + colSwap) / 2; } // Driver Code public static void main (String[] args) { // Given matrix int[][] M = { { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function Call int ans = minSwaps(M); // Print answer System.out.println(ans); }}// This code is contributed by rohitsingh07052 |
Python3
# Python3 program for the above approach# Function to return number of moves# to convert matrix into chessboarddef minSwaps(b): # Size of the matrix n = len(b) # Traverse the matrix for i in range(n): for j in range(n): if (b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]): return -1 # Initialize rowSum to count 1s in row rowSum = 0 # Initialize colSum to count 1s in column colSum = 0 # To store no. of rows to be corrected rowSwap = 0 # To store no. of columns to be corrected colSwap = 0 # Traverse in the range [0, N-1] for i in range(n): rowSum += b[i][0] colSum += b[0][i] rowSwap += b[i][0] == i % 2 colSwap += b[0][i] == i % 2 # Check if rows is either N/2 or # (N+1)/2 and return -1 if (rowSum != n // 2 and rowSum != (n + 1) // 2): return -1 # Check if rows is either N/2 # or (N+1)/2 and return -1 if (colSum != n // 2 and colSum != (n + 1) // 2): return -1 # Check if N is odd if (n % 2 == 1): # Check if column required to be # corrected is odd and then # assign N-colSwap to colSwap if (colSwap % 2): colSwap = n - colSwap # Check if rows required to # be corrected is odd and then # assign N-rowSwap to rowSwap if (rowSwap % 2): rowSwap = n - rowSwap else: # Take min of colSwap and N-colSwap colSwap = min(colSwap, n - colSwap) # Take min of rowSwap and N-rowSwap rowSwap = min(rowSwap, n - rowSwap) # Finally return answer return (rowSwap + colSwap) // 2# Driver Codeif __name__ == "__main__": # Given matrix M = [ [ 0, 1, 1, 0 ], [ 0, 1, 1, 0 ], [ 1, 0, 0, 1 ], [ 1, 0, 0, 1 ] ] # Function Call ans = minSwaps(M) # Print answer print(ans)# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;class GFG { // Function to return number of moves // to convert matrix into chessboard public static int minSwaps(int[,] b) { // Size of the matrix int n = b.GetLength(0); // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((b[0, 0] ^ b[0, j] ^ b[i, 0] ^ b[i, j]) == 1) { return -1; } } } // Initialize rowSum to count 1s in row int rowSum = 0; // Initialize colSum to count 1s in column int colSum = 0; // To store no. of rows to be corrected int rowSwap = 0; // To store no. of columns to be corrected int colSwap = 0; // Traverse in the range [0, N-1] for (int i = 0; i < n; i++) { rowSum += b[i, 0]; colSum += b[0, i]; int cond1 = 0; int cond2 = 0; if(b[i, 0] == i % 2) cond1 = 1; if(b[0, i] == i % 2) cond2 = 1; rowSwap += cond1; colSwap += cond2; } // Check if rows is either N/2 or // (N+1)/2 and return -1 if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1; // Check if rows is either N/2 // or (N+1)/2 and return -1 if (colSum != n / 2 && colSum != (n + 1) / 2) return -1; // Check if N is odd if (n % 2 == 1) { // Check if column required to be // corrected is odd and then // assign N-colSwap to colSwap if ((colSwap % 2) == 1) colSwap = n - colSwap; // Check if rows required to // be corrected is odd and then // assign N-rowSwap to rowSwap if ((rowSwap % 2) == 1) rowSwap = n - rowSwap; } else { // Take min of colSwap and N-colSwap colSwap = Math.Min(colSwap, n - colSwap); // Take min of rowSwap and N-rowSwap rowSwap = Math.Min(rowSwap, n - rowSwap); } // Finally return answer return (rowSwap + colSwap) / 2; } // Driver Code public static void Main(String[] args) { // Given matrix int[,] M = { { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function Call int ans = minSwaps(M); // Print answer Console.WriteLine(ans); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program for the above approach // Function to return number of moves // to convert matrix into chessboard function minSwaps(b) { // Size of the matrix var n = b.length; // Traverse the matrix for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if ((b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) == 1) { return -1; } } } // Initialize rowSum to count 1s in row var rowSum = 0; // Initialize colSum to count 1s in column var colSum = 0; // To store no. of rows to be corrected var rowSwap = 0; // To store no. of columns to be corrected var colSwap = 0; // Traverse in the range [0, N-1] for (i = 0; i < n; i++) { rowSum += b[i][0]; colSum += b[0][i]; var cond1 = 0; var cond2 = 0; if(b[i][0] == i % 2) cond1 = 1; if(b[0][i] == i % 2) cond2 = 1; rowSwap += cond1; colSwap += cond2; } // Check if rows is either N/2 or // (N+1)/2 and return -1 if (rowSum != n / 2 && rowSum != (n + 1) / 2) return -1; // Check if rows is either N/2 // or (N+1)/2 and return -1 if (colSum != n / 2 && colSum != (n + 1) / 2) return -1; // Check if N is odd if (n % 2 == 1) { // Check if column required to be // corrected is odd and then // assign N-colSwap to colSwap if ((colSwap % 2) == 1) colSwap = n - colSwap; // Check if rows required to // be corrected is odd and then // assign N-rowSwap to rowSwap if ((rowSwap % 2) == 1) rowSwap = n - rowSwap; } else { // Take min of colSwap and N-colSwap colSwap = Math.min(colSwap, n - colSwap); // Take min of rowSwap and N-rowSwap rowSwap = Math.min(rowSwap, n - rowSwap); } // Finally return answer return (rowSwap + colSwap) / 2; } // Driver Code var M = [[ 0, 1, 1, 0 ], [ 0, 1, 1, 0 ], [ 1, 0, 0, 1 ], [ 1, 0, 0, 1 ] ];// Function Callvar ans = minSwaps(M);// Print answerdocument.write(ans);// This code contributed by Princi Singh </script> |
Output:
2
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!
