Last Updated: 17 Apr, 2021

Transform The Matrix

Easy

Asked in companies

Solve now

Problem statement

You are given an N * N binary matrix 'MAT'. You can do two operations in the matrix:

i) Swap any two rows.
ii) Swap any two columns.

Your task is to find the minimum number of operations needed to convert this matrix into a chessboard matrix.

If the task is impossible print -1.

Note:

A chessboard matrix is a binary matrix where there are no two 0’s and no two 1’s who are adjacent to each other.

For example:

[ [1, 0], [0, 1] ] and [ [0, 1], [1, 0] ]  are chessboard matrix whereas [ [1,0], [1, 1] ] isn’t.

Input Format:

The first line of the input contains ‘T’, denoting the number of test cases.

The first line of each test case contains an integer, ‘N’ denoting dimensions of the matrix.

Next ‘N’ lines contains, N space-separated integers MAT[i][j].

Output Format:

For each test case, print the minimum number of operations to convert the given matrix into a chessboard matrix.

Note:

Don't print anything it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 3
1 <= N <= 3000
0 <= MAT[i][j] <= 1

Time Limit: 1sec

Solve now

Approaches

01 Approach

Explanation:

In a valid chessboard matrix, there are only two kinds of rows, one is the first row and one is inverse to the first row ( i.e. there are at most only two unique rows, and one is inverse of the other).
For example, if there is a row 0101 on the board, any other row must be either 0101 or 1010.
The same goes for columns.
A corollary is that any rectangle inside the board with corners top left, top right, bottom left, the bottom right must be 4 zeros or 2 ones 2 zeros or 4 zeros, i.e. even number of 1’s.
If N is even, then every row and every column has N/2 ones and N/2 zeros.
If N is odd, every row and every column has N/2 ones and N/2 + 1 zeros or N/2 + 1 ones and N/2 zeros.
These conditions are necessary and sufficient conditions for a valid chessboard matrix.
So because of the property when we arrange the first row(by swapping columns), we are actually arranging all the rows, similarly, if we arrange the first column all other columns will also be arranged.
If ‘N’ is even, we can arrange the first rows in two possible ways, eg: 1010 or 0101. So we take the minimum swaps possible because of these two transformations. If one takes ‘K’ swaps, the other can be viewed as ‘N’-’K’ swaps.
If ‘N’ is odd, then we take the even swaps because when we make a swap, we move 2 columns or 2 rows at the same time.

Algorithm is as follows:

Create variable ‘ROWSUM’= 0, ‘COLSUM’, ‘ROWSWAP’=0, ‘COLSWAP’ =0.
Check whether corners of the rectangle (0,0) (i,0), (0,j) and (i,j) have an even number of 1’s ( from the corollary in explanation ). You can take sum or check using calculation XOR of four corners. If the sum/xor is odd then print -1, it means it is impossible to transform the matrix.
Store sum of row - 1 in ‘ROWSUM’ and sum of column - 1 in ‘COLSUM’.
If 'N' is even, ‘ROWSUM’ should be equal to ‘COLSUM’ equal to 'N' / 2. If not then print -1.
If ‘N’ is odd, one of the either ‘ROWSUM’ or ‘COLSUM’ should be 'N' / 2 + 1 and the other should be 'N' / 2. If not then print -1.
For the first row calculate ‘COLSWAP’, by assuming at position (0, 'i'), 'i' % 2 should be present, i.e. the first row should be like 010101.
Similarly, calculate the ‘COLSWAP’ assuming at ('i',0), 'i' % 2 should be present.
If 'N' is even take ‘ROWSWAP’ = min('ROWSWAP', ‘N’ - ‘ROWSWAP’) and ‘COLSWAP’ = min('COLSWAP', 'N' - 'COLSWAP' ).
If 'N' is odd, if ‘COLSWAP’ is odd, then make it even i.e. ‘COLSWAP’= 'N' - ‘COLSWAP’, and if ‘ROWSWAP’ is odd, make it even, ‘ROWSWAP’= ‘N’ - ‘ROWSWAP’.
Return ‘COLSWAP’ / 2 + ‘ROWSWAP’ / 2.

Solve now