Matrix Flip Bit
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

Question

Matrix Flip Bit

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:

insert eg 1

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.

insert eg 2

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

Accepted Answer

I first applied brute force but the solution was exceeding the time limit so I looked for ways to avoid traversing every
row and column of the matrix. Take the input of the matrix and in a map stored the location of every 0 in the original matrix. Then I traversed through the matrix whenever I encountered a 0 I traversed through its row and column and counted the number of ones. I also marked the row and column visited on the map to make sure I don't visit them again to reduce the time complexity.

Accepted Answer

Brute Force Approach

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’.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space to store the elements.

Time Complexity: O(n^3)Explanation:

O(N ^ 3), where ‘N’ is the number of rows and columns of the matrix ‘MAT’.

In the worst case, we can have all 0s and in that case, each element will have an order of ‘N’ loop so the overall complexity will be the order of O(N ^ 3).

C++ (g++ 5.4)

/*

	Time Complexity: O(N ^ 3)

	Space Complexity: O(1)



	Where 'N' is the number of rows and columns in matrix 'MAT'.

*/



int countFlip(vector> &mat)

{

	int n = mat.size();



	// Mark the flipped bits as -1 and increment count.

	int count = 0;



	for (int i = 0; i < n; i++)

	{

		for (int j = 0; j < n; j++)

		{

			if (mat[i][j] == 0)

			{

				// Use 'k' as a variable to iterate through row and column.

				for (int k = 0; k < n; k++)

				{

					// Check every column.

					if (mat[i][k] == 1)

					{

						count++;

						mat[i][k] = -1;

					}

					// Check every row.

					if (mat[k][j] == 1)

					{

						count++;

						mat[k][j] = -1;

					}

				}

			}

		}

	}



	return count;

}

Python (3.5)

'''

    Time Complexity: O(N ^ 3)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the sequence.

'''



def countFlip(mat):

    n = len(mat)



    # Mark the flipped bits as -1 and increment count.

    count = 0

    for i in range(n):

        for j in range(n):

            if (mat[i][j] == 0):

                # Use 'k' as a variable to iterate through row and column.

                for k in range(n):

                    

                    # Check every column.

                    if (mat[i][k] == 1):

                        count += 1

                        mat[i][k] = -1



                    # Check every row.

                    if (mat[k][j] == 1):

                        count += 1

                        mat[k][j] = -1



    return count

Java (SE 1.8)

/*
	Time Complexity: O(N ^ 3)
	Space Complexity: O(1)

	Where 'N' is the number of rows and columns in matrix 'MAT'.
*/

public class Solution {
	public static int countFlip(int[][] mat) {
		int n = mat.length;

		// Mark the flipped bits as -1 and increment count.
		int count = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (mat[i][j] == 0) {
					
					// Use 'k' as a variable to iterate through row and column.
					for (int k = 0; k < n; k++) {
						
						// Check every column.
						if (mat[i][k] == 1) {
							count++;
							mat[i][k] = -1;
						}
						
						// Check every row.
						if (mat[k][j] == 1) {
							count++;
							mat[k][j] = -1;
						}
					}
				}
			}
		}

		return count;
	}
}

Accepted Answer

Optimised Approach

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’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of rows and columns of the matrix ‘MAT’.

We need two visited arrays to store that if any particular row or column is visited or not.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of rows and columns of the matrix ‘MAT’.

We need to go through all the elements in the matrix and the matrix has N * N elements. Therefore the final time complexity is O(N ^ 2).

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(N)



    Where 'N' is the number of rows and columns in matrix 'MAT'.

*/



import java.util.ArrayList;



class Pair {

	public T first;

	public P second;



	public Pair(T f, P s) {

		first = f;

		second = s;

	}

}



public class Solution {

	public static int countFlip(int[][] mat) {



		int n = mat.length;



		// Initialise both visited row and col as false.

		boolean[] visitedRow = new boolean[n];

		boolean[] visitedCol = new boolean[n];

		int count = 0;

		ArrayList> s = new ArrayList<>();



		for (int i = 0; i < n; i++) {

			for (int j = 0; j < n; j++) {

				if (mat[i][j] == 0) {

					s.add(new Pair(i, j));

				}

			}

		}



		for (Pair element : s) {

			

			// Fixing column.

			if (visitedCol[element.second] == false) {

				for (int k = 0; k < n; k++) {

					if (mat[k][element.second] == 1) {

						count++;

						mat[k][element.second] = -1;

					}



					if (k == n - 1) {

						visitedCol[element.second] = true;

					}

				}

			}

			

			// Fixing row.

			if (visitedRow[element.first] == false) {

				for (int k = 0; k < n; k++) {

					if (mat[element.first][k] == 1) {

						count++;

						mat[element.first][k] = -1;

					}



					if (k == n - 1) {

						visitedRow[element.first] = true;

					}

				}

			}

		}



		return count;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(N)



    Where 'N' is the number of rows and columns in matrix 'MAT'.

*/



int countFlip(vector> &mat)

{

    int n = mat.size();



    // Initialise both visited row and col as 0.

    vector visitedRow(n, false), visitedCol(n, false);



    int count = 0;

    vector> s;



    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            if (mat[i][j] == 0)

            {

                s.push_back(make_pair(i, j));

            }

        }

    }



    for (auto element : s) {

        // Fixing column.

        if (visitedCol[element.second] == false)

        {

            for (int k = 0; k < n; k++)

            {

                if (mat[k][element.second] == 1)

                {

                    count++;

                    mat[k][element.second] = -1;

                }



                if (k == n - 1) {

                    visitedCol[element.second] = true;

                }

            }

        }

        // Fixing row.

        if (visitedRow[element.first] == 0)

        {

            for (int k = 0; k < n; k++)

            {

                if (mat[element.first][k] == 1)

                {

                    count++;

                    mat[element.first][k] = -1;

                }



                if (k == n - 1) {

                    visitedRow[element.first] = true;

                }

            }

        }

    }



    return count;

}

Python (3.5)

'''

    Time Complexity: O(N ^ 2)

    Space Complexity: O(N)



    Where 'N' is the number of elements in the sequence.

'''



def countFlip(mat):

    n = len(mat)

    

    # Initialise both visited row and col as 0.

    visitedRow = [False for i in range(n)]

    visitedCol = [False for i in range(n)]

    count = 0

    s = []

    for i in range(n):

        for j in range(n):

            if (mat[i][j] == 0):

                s.append([i, j])



    for element in s:



        # Fixing column.

        if (visitedCol[element[1]] == False):

            for k in range(n):



                if (mat[k][element[1]] == 1):

                    count += 1

                    mat[k][element[1]] = -1



                if (k == n - 1):

                    visitedCol[element[1]] = True



        # Fixing row.

        if (visitedRow[element[0]] == 0):

            for k in range(n):

                if (mat[element[0]][k] == 1):

                    count += 1

                    mat[element[0]][k] = -1



                if (k == n - 1):

                    visitedRow[element[0]] = True



    return count

Accepted Answer

Deriving a formula

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.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space to store elements.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of rows and columns of the matrix ‘MAT’.

We need to go through all the elements in the matrix and the matrix has N * N elements. Therefore the final time complexity is O(N ^ 2).

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2)

    Space Complexity: O(1)



    Where 'N' is the number of rows and columns in matrix 'MAT'.

*/



public class Solution {

	public static int countFlip(int[][] mat) {

		int n = mat.length, row = 0, col = 0, zeros = 0;



		for (int i = 0; i < n; i++) {

			for (int j = 0; j < n; j++) {

				if (mat[i][j] == 0) {

					zeros++;

				}

			}

		}



		for (int i = 0; i < n; i++) {

			for (int j = 0; j < n; j++) {

				if (mat[i][j] == 0) {

					row++;

					break;

				}

			}

		}



		for (int i = 0; i < n; i++) {

			for (int j = 0; j < n; j++) {

				if (mat[j][i] == 0) {

					col++;

					break;

				}

			}

		}



		int res = (n * row) + ((n - row) * col) - zeros;



		return res;

	}

}

Python (3.5)

'''

	Time Complexity : O(N ^ 2)

	Space Complexity : O(1)



	Where 'N' is the number of rows and columns in matrix 'MAT'.

'''



def countFlip(mat):

	n = len(mat)

	row, col, zeros = 0, 0, 0



	for i in range(n):

		for j in range(n):

			if (mat[i][j] == 0):

				zeros += 1



	for i in range(n):

		for j in range(n):

			if (mat[i][j] == 0):

				row += 1

				break



	for i in range(n):

		for j in range(n):

			if (mat[j][i] == 0):

				col += 1

				break



	res = (n * row) + ((n - row) * col) - zeros



	return res

C++ (g++ 5.4)

/*

	Time Complexity : O(N ^ 2)

	Space Complexity : O(1)



	Where 'N' is the number of rows and columns in matrix 'MAT'.

*/



int countFlip(vector> &mat)

{

	int n = mat.size(), row = 0, col = 0, zeros = 0;



	for (int i = 0; i < n; i++)

	{

		for (int j = 0; j < n; j++)

		{

			if (mat[i][j] == 0)

			{

				zeros++;

			}

		}

	}



	for (int i = 0; i < n; i++)

	{

		for (int j = 0; j < n; j++)

		{

			if (mat[i][j] == 0)

			{

				row++;

				break;

			}

		}

	}



	for (int i = 0; i < n; i++)

	{

		for (int j = 0; j < n; j++)

		{

			if (mat[j][i] == 0)

			{

				col++;

				break;

			}

		}

	}



	int res = (n * row) + ((n - row) * col) - zeros;



	return res;

}

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:

For example:

Input format:

Output format:

Note:

Constraints:

Top Deutsche Bank Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Deutsche Bank Software Developer Intern