Transform The Matrix

Easy
0/40
Average time to solve is 10m
profile
Contributed by
2 upvotes
Asked in companies
OLX GroupChegg Inc.Barclays

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
0 1 1 0
0 1 1 0
1 0 0 1
1 0 0 1
2
1 0
1 0
Sample Output 1:
2
-1
Explanation for Sample Input 1:
In test case 1:

Swap column 1 and column 2.

| 0 1 1 0 |      | 1 0 1 0 |
| 0 1 1 0 |  =   | 1 0 1 0 |
| 1 0 0 1 |      | 0 1 0 1 |
| 1 0 1 1 |      | 0 1 0 1 |

Swap row 2 and row 3.

| 1 0 1 0 |      | 1 0 1 0 |
| 1 0 1 0 |  =   | 0 1 0 1 |
| 0 1 0 1 |      | 1 0 1 0 |
| 0 1 1 1 |      | 0 1 0 1 |

Minimum 2 operations are required for the transformation.

In test case 2, It is impossible to convert the matrix into a chessboard matrix.
Sample Input 2:
2
6
0 0 1 1 0 1 
1 1 0 0 1 0 
1 1 0 0 1 0 
0 0 1 1 0 1 
0 0 1 1 0 1 
1 1 0 0 1 0 
4
1 0 1 0 
0 1 0 1 
1 0 1 0 
0 1 0 1
Sample Output 2:
2
0
Explanation for Sample Input 2:
In the first test case, we need two operations to convert it into required chessboard matrix.

In the second test case, the given matrix is required matrix only.
Hint

There are only two possible unique rows and columns, where one is an inversion of the other.

Approaches (1)
Brute Force

Explanation:

  1. 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).
  2. For example, if there is a row 0101 on the board, any other row must be either 0101 or 1010.
  3. The same goes for columns.
  4. 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.
  5. If N is even, then every row and every column has N/2 ones and N/2 zeros.
  6. 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.
  7. These conditions are necessary and sufficient conditions for a valid chessboard matrix.
  8. 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.
  9. 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.
  10. 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:

  1. Create variable ‘ROWSUM’= 0, ‘COLSUM’, ‘ROWSWAP’=0, ‘COLSWAP’ =0.
  2. 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.
  3. Store sum of row - 1 in ‘ROWSUM’ and sum of column - 1 in ‘COLSUM’.
  4. If 'N' is even, ‘ROWSUM’ should be equal to ‘COLSUM’ equal to 'N' / 2. If not then print -1.
  5. 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.
  6. 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.
  7. Similarly, calculate the ‘COLSWAP’ assuming at ('i',0), 'i' % 2 should be present.
  8. If 'N' is even take ‘ROWSWAP’ = min('ROWSWAP', ‘N’ - ‘ROWSWAP’) and ‘COLSWAP’ = min('COLSWAP', 'N' - 'COLSWAP' ).
  9. 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’.
  10. Return ‘COLSWAP’ / 2 + ‘ROWSWAP’ / 2.
Time Complexity

O( N^2 ), where N is the dimension of the matrix

 

We need to iterate over the whole matrix, thus time complexity is O(N^2)

Space Complexity

O(1)

 

No additional memory is required.

Code Solution
(100% EXP penalty)
Transform The Matrix
Full screen
Console