Given a matrix of size N * N containing only 0s and 1s, where 0 represents white and 1 represents black. The task is to minimize the number of swaps to form a valid chessboard. Only 2 rows or 2 columns can be swapped with each other.
If it is impossible to form a chessboard, return -1.
Examples:
Input: {{0, 1, 1, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}}
Output: 2
Explanation: One potential sequence of moves is shown below,
The first move swaps the first and second columns.
The second move swaps the second and third row.Input: {{0, 1, 0}, {1, 0, 1}, {1, 1, 0}}
Output: -1
Approach: The problem can be solved based on the following properties of chessboard and the observation:
Properties of chess board:
- In a valid chess board, there are 2 and only 2 kinds of rows and one is inverse to the other, the same is true for columns.
A corollary is that any rectangle inside the board with corners top left, top right, bottom left, and bottom right must be 4 zeros or 2 ones and 2 zeros or 4 zeros.- Another important property is that every row and column has half ones. Assume the board is N * N:
- If N = 2 * K, every row and every column has K ones and K zeros.
- If N = 2 * K + 1, every row and every column has K ones and K + 1 zeros or K + 1 ones and K zeros.
Since the swap process does not break these properties, for a given board to be valid, these properties must hold.
These two conditions are necessary and sufficient conditions for a valid chessboard.Swap Count:
To calculate the number of swaps required to create the chessboard, Iterating over first row and first column and check for alternate whites and blacks.
Follow the steps mentioned below to implement the idea:
- Initially, check whether the board is valid or not using the properties of the chessboard, if the board is valid we proceed otherwise -1 is returned.
- Iterate over the first row and the first column and count the number of 1s in both and also count the number of swaps required using the condition, A[i] = i%2 .
- Use the number of ones calculated to verify the second property of the chessboard (i.e. every row and column has half ones), if the board is invalid return -1 otherwise proceed further.
- Now if N is even, then the minimum swaps are stored as they are.
- If N is Odd, then we take the even swaps as we can swap 2 rows or 2 columns only.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to return minimum swapsint movesToChessboard(vector<vector<int> >& board){ int n = board.size(); // Loop to check whether the board // can be made valid or not for (int r = 0; r < n; r++) { for (int c = 0; c < n; c++) { if (board[0][0] ^ board[r][0] ^ board[0] ^ board[r] == 1) { return -1; } } } int rowsum = 0; int colsum = 0; int rowswap = 0; int colswap = 0; // Loop to calculate sum and swap for (int i = 0; i < n; i++) { rowsum += board[i][0]; colsum += board[0][i]; rowswap += board[i][0] == i % 2; colswap += board[0][i] == i % 2; } // If there are more white or more black if (rowsum != n / 2 and rowsum != (n + 1) / 2) return -1; if (colsum != n / 2 and colsum != (n + 1) / 2) return -1; // If n is odd if (n % 2) { if (rowswap % 2) rowswap = n - rowswap; if (colswap % 2) colswap = n - colswap; } // If n is even else { rowswap = min(rowswap, n - rowswap); colswap = min(colswap, n - colswap); } // Return the ans return (rowswap + colswap) / 2;}// Driver Codeint main(){ // Given vector array vector<vector<int> > arr{ { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function call int minswap = movesToChessboard(arr); // Printing the output if (minswap == -1) cout << "Impossible"; else cout << minswap << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to return minimum swaps public static int movesToChessboard(int board[][]) { int n = board.length; // Loop to check whether the board // can be made valid or not for (int r = 0; r < n; r++) { for (int c = 0; c < n; c++) { if ((board[0][0] ^ board[r][0] ^ board[0] ^ board[r]) == 1) { return -1; } } } int rowsum = 0; int colsum = 0; int rowswap = 0; int colswap = 0; // Loop to calculate sum and swap for (int i = 0; i < n; i++) { rowsum += board[i][0]; colsum += board[0][i]; if (i % 2 != 0) { rowswap += board[i][0]; colswap += board[0][i]; } } // If there are more white or more black if (rowsum != n / 2 && rowsum != (n + 1) / 2) return -1; if (colsum != n / 2 && colsum != (n + 1) / 2) return -1; // If n is odd if (n % 2 != 0) { if (rowswap % 2 != 0) rowswap = n - rowswap; if (colswap % 2 != 0) colswap = n - colswap; } // If n is even else { rowswap = Math.min(rowswap, n - rowswap); colswap = Math.min(colswap, n - colswap); } // Return the ans return (rowswap + colswap + 2) / 2; } // Driver Code public static void main(String[] args) { // Given vector array int arr[][] = { { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function call int minswap = movesToChessboard(arr); // Printing the output if (minswap == -1) System.out.print("Impossible"); else System.out.print(minswap); }}// This code is contributed by Rohit Pradhan |
Python3
# python3 code to implement the approach# Function to return minimum swapsdef movesToChessboard(board): n = len(board) # Loop to check whether the board # can be made valid or not for r in range(0, n): for c in range(0, n): if (board[0][0] ^ board[r][0] ^ board[0] ^ board[r] == 1): return -1 rowsum = 0 colsum = 0 rowswap = 0 colswap = 0 # Loop to calculate sum and swap for i in range(0, n): rowsum += board[i][0] colsum += board[0][i] rowswap += board[i][0] == i % 2 colswap += board[0][i] == i % 2 # If there are more white or more black if (rowsum != n // 2 and rowsum != (n + 1) // 2): return -1 if (colsum != n // 2 and colsum != (n + 1) // 2): return -1 # If n is odd if (n % 2): if (rowswap % 2): rowswap = n - rowswap if (colswap % 2): colswap = n - colswap # If n is even else: rowswap = min(rowswap, n - rowswap) colswap = min(colswap, n - colswap) # Return the ans return (rowswap + colswap) // 2# Driver Codeif __name__ == "__main__": # Given vector array arr = [[0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1]] # Function call minswap = movesToChessboard(arr) # Printing the output if (minswap == -1): print("Impossible") else: print(minswap) # This code is contributed by rakeshsahni |
C#
// C# program for above approach:using System;class GFG { // Function to return minimum swaps public static int movesToChessboard(int[,] board) { int n = board.GetLength(0); // Loop to check whether the board // can be made valid or not for (int r = 0; r < n; r++) { for (int c = 0; c < n; c++) { if ((board[0,0] ^ board[r,0] ^ board[0,c] ^ board[r,c]) == 1) { return -1; } } } int rowsum = 0; int colsum = 0; int rowswap = 0; int colswap = 0; // Loop to calculate sum and swap for (int i = 0; i < n; i++) { rowsum += board[i,0]; colsum += board[0,i]; if (i % 2 != 0) { rowswap += board[i,0]; colswap += board[0,i]; } } // If there are more white or more black if (rowsum != n / 2 && rowsum != (n + 1) / 2) return -1; if (colsum != n / 2 && colsum != (n + 1) / 2) return -1; // If n is odd if (n % 2 != 0) { if (rowswap % 2 != 0) rowswap = n - rowswap; if (colswap % 2 != 0) colswap = n - colswap; } // If n is even else { rowswap = Math.Min(rowswap, n - rowswap); colswap = Math.Min(colswap, n - colswap); } // Return the ans return (rowswap + colswap + 2) / 2; } // Driver Code public static void Main() { // Given vector array int[,] arr = { { 0, 1, 1, 0 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 } }; // Function call int minswap = movesToChessboard(arr); // Printing the output if (minswap == -1) Console.Write("Impossible"); else Console.Write(minswap); }}// This code is contributed by code_hunt. |
Javascript
<script>//Javascript code for the above approach// Function to return minimum swapsfunction movesToChessboard( board){ let n = board.length; // Loop to check whether the board // can be made valid or not for (let r = 0; r < n; r++) { for (let c = 0; c < n; c++) { if (board[0][0] ^ board[r][0] ^ board[0] ^ board[r] == 1) { return -1; } } } let rowsum = 0; let colsum = 0; let rowswap = 0; let colswap = 0; // Loop to calculate sum and swap for (let i = 0; i < n; i++) { rowsum += board[i][0]; colsum += board[0][i]; rowswap += board[i][0] == i % 2; colswap += board[0][i] == i % 2; } // If there are more white or more black if (rowsum != n / 2 && rowsum != (n + 1) / 2) return -1; if (colsum != n / 2 && colsum != (n + 1) / 2) return -1; // If n is odd if (n % 2) { if (rowswap % 2) rowswap = n - rowswap; if (colswap % 2) colswap = n - colswap; } // If n is even else { rowswap = Math.min(rowswap, n - rowswap); colswap = Math.min(colswap, n - colswap); } // Return the ans return (rowswap + colswap) / 2;}// Driver Code //2d array let arr = [ [ 0, 1, 1, 0 ], [ 0, 1, 1, 0 ], [ 1, 0, 0, 1 ], [ 1, 0, 0, 1 ]]; // Function call let minswap = movesToChessboard(arr); // Printing the output if (minswap == -1) document.write( "Impossible"); else document.write(minswap); // This code is contributed by hrithikgarg03188.</script> |
Output
2
Time complexity: O(N2)
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!
