RUN


Count number of zeros in a Row-wise Col-wise sorted binary matrix

Given: a binary matrix with sorted rows and columns.

Example: If the matrix is :

[0, 0, 0, 1]

[0, 0, 1, 1]

[0, 1, 1, 1]

[1, 1, 1, 1]

Then output should be 6, because there are 6 zeros in the matrix.

# Approach

The entire matrix is traversed and the count of zeros is incremented.

Code:

#include <iostream>

// C++ program to count number of 0s in the given

// row-wise and column-wise sorted binary matrix.

// define size of square matrix

const int N = 5;

// Function to count number of 0s in the given

// row-wise and column-wise sorted binary matrix.

int zerocount(int mat[N][N])

{

	// starting from bottom -left corner of matrix

	int rows = N - 1, column = 0;

	// variable storing number of zeroes

	int count = 0;

	while (column < N)

	{

		// going up till we find a 0

		while (mat[rows][column])

			// if zero is not found in present column,
			//we are done

			if (--rows < 0)

				return count;

		// add number of 0s present in current column to the answer

		count += (rows + 1);

		// moving right to next the column

		column++;
	}

	return count;

}

// main function

int main()

{

	int mat[N][N] =

		{

			{ 0, 0, 0, 0, 0 },
			{ 0, 0, 0, 1, 1 },
			{ 0, 0, 0, 1, 1 },
			{ 0, 0, 1, 1, 1 },
			{ 1, 1, 1, 1, 1 }
		};

	std::cout << zerocount(mat);

	return 0;

}

TIME COMPLEXITY: The time complexity of this code is O(n2)

Report Error/ Suggestion

Related Posts:

[yuzo_views]



Interview Questions



CopyRight © 2020

CopyRight © 2020