Last Updated: 4 Dec, 2020
Matrix Flip Bit
Easy
Asked in companies
You have been given a binary matrix ‘MAT’ of size ‘N’ * ’N’. Let ‘i’, ’j’ denote the row and column of the matrix, respectively. If ‘MAT’[i][j] is equal to 0, flip every 1 in the ‘i’th row and ‘j’th column i.e., in the same row and the column as 0.
Your task is to return the total number of flips done over all the elements of the matrix.
Note:
1. Each element in the matrix 'MAT' is either a ‘0’ or ‘1.’
2. The flip operation is performed only for the 0s in the original matrix, and not for the new 0s formed as a result of flipping 1s in the original matrix.
3. If a cell is already flipped, don’t flip it twice.
4. Return the minimum number of flips needed.
For example:
Let the matrix be:
Then we return 6. As shown in the figure, the cells marked in red will be counted as they lie in the same row or column as 0 and will be flipped.
Input format:
The first line of input contains ‘T’ denoting the number of test cases.
The first line of each test case contains ‘N’ denoting the dimensions of the ‘N * N’ matrix.
The next ‘N’ lines contain ‘N’ single space-separated integers denoting the matrix 'MAT’.
Output format:
For each test case, print a single line that contains an integer that denotes the total number of flips made.
Note:
You don't have to print the output it has been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
0 <= N <= 100
MAT[i][j] = 0 or 1
Where ‘T’ is the number of test cases and ‘N’ is the number of rows and columns of the matrix 'MAT'.
Time limit: 1 sec
Approaches
The main idea is to count the number of 1s in the same row or column as any of the 0 in the given matrix. To do that, we iterate through the matrix with the variable ‘i’ for the row and ‘j’ for the column, and if for any cell ‘MAT’[i][j] = 0, we iterate through the ‘i’th row and ‘j’th column and count the number of 1s in them and mark them as -1 so that we do not revisit them. Finally, we return the ‘COUNT’.
- Take a variable ‘COUNT’ to count the number of bits to be flipped.
- Iterate through the matrix with the variable ‘i’ for row and variable ‘j’ for column and check for each matrix element if ‘MAT’[i][j] is zero.
- If ‘MAT’[i][j] is zero, we iterate in the ‘i'th row and ‘j’th column using a variable ‘k’ and increment the count if ‘MAT’[i][k] or ‘MAT’[k][j] is 1.
- If the above conditions are satisfied, we also mark the cell as -1 to not count it again.
- Finally, we return the ‘COUNT’.
The main idea is to ensure that a particular row or column is already checked, we need not check it again. We can do this by maintaining a visited array for rows and columns and checking every time we encounter a ‘0’ that if its row or column is already visited then we need not check it again.
Keeping the above idea in mind, we can have the following approach:
- Make two arrays ‘VISITED_ROW’ and ‘VISITED_COL’ each of size ‘N’ to store if any particular row is already checked or not, where ‘N’ is the number of rows and number of columns.
- Then we traverse the matrix and store the position of the zeroes in an array of pairs.
- We traverse the vector and for each element if the element is a ‘0’ we add its row and column position as a pair in the array.
- Then we traverse the array with the position of zeroes and for each element of the array, we check if columns and rows are visited or not.
- If not visited, we traverse the particular row or column and check the number of 1s in the column or row and increment the count and replace the 1 with -1 so we do not count it again.
- Finally, we return the ‘COUNT’.
The main idea is to calculate the number of zeros in the matrix, the number of rows that have zero, and the number of columns that have zeros.
Then the final answer = (ROWS * N) + ((N - ROWS) * COLS) - ZEROES.
- Maintain three variables ‘ZEROS’, ‘ROWS’,’ COL’ which represent the number of zeros in the matrix, the number of rows that have zero, and a number of columns that have zeros respectively.
- Loop through the matrix to calculate the ‘ZEROS’, ‘ROWS’, ‘COLS’.
- Then the final answer is stored in ‘RES’.
- ‘RES’ = (‘ROWS’ * ‘N’) + ((‘N’ - ‘ROWS’) * ‘COLS) - ‘ZEROS’.
- Return ‘RES’ as the final answer.