Given two binary matrices, A[][] and B[][] of size N×M, the task is to find the minimum number of swaps of the elements of matrix A, needed to convert matrix A into matrix B. If it is impossible to do so then print “-1“.
Examples :
Input: A[][] = {{1, 1, 0}, {0, 0, 1}, {0, 1, 0}}, B[][] = {{0, 0, 1}, {0, 1, 0}, {1, 1, 0}}
Output: 3
Explanation:
One possible way to convert matrix A into B is:
- Swap the element A[0][0] with A[0][2]. Thereafter the matrix A modifies to {{ 0, 1, 1}, {0, 0, 1}, {0, 1, 0}}.
- Swap the element A[0][1] with A[1][1]. Thereafter the matrix A modifies to {{ 0, 0, 1}, {0, 1, 1}, {0, 1, 0}}.
- Swap the element A[1][2] with A[2][0]. Thereafter the matrix A modifies to {{ 0, 0, 1}, {0, 1, 0}, {1, 1, 0}}.
Therefore, the total number of moves needed is 3 and also it is the minimum number of moves needed.
Input: A[][] = {{1, 1}, {0, 1}, {1, 0}, {0, 0}}, B[][] = {{1, 1}, {1, 1}, {0, 1}, {0, 0}}
Output: -1
Naive Approach: This problem can be solved using Hashing. To convert matrix A to B by only swaps, the count of set bits and unset bits in both the matrices must be same. So first check if the set bits and unset bits in A is same as in B or not. If yes, then find the number of positions where element in A is not same as element in B. This will be the final count.
Efficient Approach: The above approach can be further space optimized, with the help of observation that count the number of elements such that A[i][j] = 0 and B[i][j] = 1 and number of elements such that A[i][j] = 1 and B[i][j] = 0 must be equal and the minimum number of moves needed is equal to the count obtained. Follow the steps below to solve the problem:
- Initialize two variable, say count10 and count01 which count the number of elements such that A[i][j] = 1 and B[i][j] = 0 and number of elements such that A{i][j] = 0 and B[i][j] = 1 respectively.
- Iterate over the range [0, N-1] using the variable i and perform the following steps:
- Iterate over the range [0, M-1] using the variable j and if A[i][j] = 1 and B[i][j] = 0 then increment the count10 by 1. Else, if A[i][j] = 0 and B[i][j] = 1 then increment the count01 by 1.
- If count01 is equal to count10, then print the value of count01 as the answer. Otherwise, print -1 as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the minimum number// of swaps required to convert matrix// A to matrix Bint minSwaps(int N, int M, vector<vector<int> >& A, vector<vector<int> >& B){ // Stores number of cells such that // matrix A contains 0 and matrix B // contains 1 int count01 = 0; // Stores number of cells such that // matrix A contains 1 and matrix B // contains 0 int count10 = 0; // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // Iterate over the range [0, M-1] for (int j = 0; j < M; j++) { if (A[i][j] != B[i][j]) { // If A[i][j] = 1 and B[i][j] = 0 if (A[i][j] == 1) count10++; // If A[i][j] = 0 and B[i][j] = 1 else count01++; } } } // If count01 is equal to count10 if (count01 == count10) return count01; // Otherwise, else return -1;}// Driver Codeint main(){ vector<vector<int> > A = { { 1, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }; vector<vector<int> > B = { { 0, 0, 1 }, { 0, 1, 0 }, { 1, 1, 0 } }; int N = A.size(); int M = B[0].size(); cout << minSwaps(N, M, A, B);} |
Java
// Java program for the above approachpublic class MyClass{ // Function to count the minimum number// of swaps required to convert matrix// A to matrix Bpublic static int minSwaps(int N, int M, int A[][], int B[][]){ // Stores number of cells such that // matrix A contains 0 and matrix B // contains 1 int count01 = 0; // Stores number of cells such that // matrix A contains 1 and matrix B // contains 0 int count10 = 0; // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // Iterate over the range [0, M-1] for (int j = 0; j < M; j++) { if (A[i][j] != B[i][j]) { // If A[i][j] = 1 and B[i][j] = 0 if (A[i][j] == 1) count10++; // If A[i][j] = 0 and B[i][j] = 1 else count01++; } } } // If count01 is equal to count10 if (count01 == count10) return count01; // Otherwise, else return -1;}// Driver Code public static void main(String args[]){ int [][] A = { { 1, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }; int [][] B = { { 0, 0, 1 }, { 0, 1, 0 }, { 1, 1, 0 } }; int N = A.length; int M = B[0].length; System.out.println(minSwaps(N, M, A, B));}}// This code is contributed by SoumikMondal |
Python3
# Python3 program for the above approach# Function to count the minimum number# of swaps required to convert matrix# A to matrix Bdef minSwaps(N, M, A, B): # Stores number of cells such that # matrix A contains 0 and matrix B # contains 1 count01 = 0 # Stores number of cells such that # matrix A contains 1 and matrix B # contains 0 count10 = 0 # Iterate over the range[0, N-1] for i in range(0, N): # Iterate over the range[0, M-1] for j in range(0, M): if (A[i][j] != B[i][j]): # If A[i][j] = 1 and B[i][j] = 0 if (A[i][j] == 1): count10 += 1 # If A[i][j] = 0 and B[i][j] = 1 else: count01 += 1 # If count01 is equal to count10 if (count01 == count10): return count01 # Otherwise, else: return -1# Driver CodeA = [ [ 1, 1, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ] ]B = [ [ 0, 0, 1 ], [ 0, 1, 0 ], [ 1, 1, 0 ] ] N = len(A)M = len(B[0])print(minSwaps(N, M, A, B))# This code is contributed by amreshkumar3 |
Javascript
<script> // JavaScript program for the above approach // Function to count the minimum number // of swaps required to convert matrix // A to matrix B function minSwaps(N, M, A, B) { // Stores number of cells such that // matrix A contains 0 and matrix B // contains 1 let count01 = 0; // Stores number of cells such that // matrix A contains 1 and matrix B // contains 0 let count10 = 0; // Iterate over the range [0, N-1] for (let i = 0; i < N; i++) { // Iterate over the range [0, M-1] for (let j = 0; j < M; j++) { if (A[i][j] != B[i][j]) { // If A[i][j] = 1 and B[i][j] = 0 if (A[i][j] == 1) count10++; // If A[i][j] = 0 and B[i][j] = 1 else count01++; } } } // If count01 is equal to count10 if (count01 == count10) return count01; // Otherwise, else return -1; } // Driver Code let A = [[1, 1, 0], [0, 0, 1], [0, 1, 0]]; let B = [[0, 0, 1], [0, 1, 0], [1, 1, 0]]; let N = A.length; let M = B[0].length; document.write(minSwaps(N, M, A, B)); // This code is contributed by Potta Lokesh </script> |
C#
// C# program for the above approachusing System;class GFG {// Function to count the minimum number// of swaps required to convert matrix// A to matrix Bpublic static int minSwaps(int N, int M, int[,] A, int[,] B){ // Stores number of cells such that // matrix A contains 0 and matrix B // contains 1 int count01 = 0; // Stores number of cells such that // matrix A contains 1 and matrix B // contains 0 int count10 = 0; // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // Iterate over the range [0, M-1] for (int j = 0; j < M; j++) { if (A[i,j] != B[i, j]) { // If A[i][j] = 1 and B[i][j] = 0 if (A[i, j] == 1) count10++; // If A[i][j] = 0 and B[i][j] = 1 else count01++; } } } // If count01 is equal to count10 if (count01 == count10) return count01; // Otherwise, else return -1;} // Driver code public static void Main (String[] args) { int [,] A = { { 1, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }; int [,] B = { { 0, 0, 1 }, { 0, 1, 0 }, { 1, 1, 0 } }; int N = A.GetLength(0); int M = 3; Console.Write(minSwaps(N, M, A, B)); }} |
Output
3
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!
