Minimum row or column swaps required to make every pair of adjacent cell of a Binary Matrix distinct

0 0 10 minutes read

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.
1. 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.
2. If rowSum is not equal to either of N/2 or (N+1)/2 then return -1.
3. If colSum is not equal to either of N/2 or (N+1)/2 then return -1.
4. 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.
5. 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 chessboard
int 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 Code
int 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 approach
import 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 chessboard
def 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 Code
if __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 approach
using 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 Call
var ans = minSwaps(M);
 
// Print answer
document.write(ans);
 
// This code contributed by Princi Singh 
 
</script>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(N²)

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 zambiatek!