{"post":"

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>\n\n// C++ program to count number of 0s in the given\n// row-wise and column-wise sorted binary matrix.\n\n// define size of square matrix\nconst int N = 5;\n\n// Function to count number of 0s in the given\n// row-wise and column-wise sorted binary matrix.\nint zerocount(int mat[N][N])\n{\n    // starting from bottom -left corner of matrix\n    int rows = N - 1, column = 0;\n\n    // variable storing number of zeroes\n    int count = 0;\n\n    while (column < N)\n    {\n        // going up till we find a 0\n        while (mat[rows][column])\n        // if zero is not found in present column,\n        //we are done\n        if (--rows < 0)\n            return count;\n\n        // add number of 0s present in current column to the answer\n        count += (rows + 1);\n\n        // moving right to next the column\n        column++;\n    }\n\n    return count;\n}\n\n// main function\nint main()\n{\n    int mat[N][N] =\n        {\n            { 0, 0, 0, 0, 0 },\n            { 0, 0, 0, 1, 1 },\n            { 0, 0, 0, 1, 1 },\n            { 0, 0, 1, 1, 1 },\n            { 1, 1, 1, 1, 1 }\n        };\n\n    std::cout << zerocount(mat);\n\n    return 0;\n}\n\n

Output

8\n\n

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

\n","title":"Count number of zeros in a Row-wise Col-wise sorted binary matrix","authorDetails":{"name":"Prabhnoor Maingi","slug":"prabhnoor-maingi"},"description":"Learn how to write a C++ program to count the number of zeros in a row-wise and column-wise sorted binary matrix. Get detailed explanations and examples of how to use loops and conditional statements to traverse the matrix and find the zeros.","slug":"count-number-of-zeros-in-a-row-wise-col-wise-sorted-binary-matrix/","articleId":"636a83447bb1ce5072622b61","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}