Given a binary matrix mat[][] of size m*n (0-based indexing), the task is to return the total number of 1’s in the matrix that follows the below two rules. i.e:

• Row R and column C both contain exactly N number of 1’s.
• All rows with 1’s in column C should be the same as the 1’s present in row R.

Examples:

Input: mat= [[0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 0], [0, 0, 1, 0, 1, 0]], N = 3
Output: 6
Explanation: All the underlined ‘1’ are the 1’s we need (all ‘1’s at column 1 and 3). [[0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 0], [0, 0, 1, 0, 1, 0]]

1. Rule 1: For each row R and column C, both should have exactly N number of “1’s” (where N = 3 in this case).
2. Rule 2: If the rows containing “1’s” at column C are the same as row R, they contribute to the count.

Let’s go through an example for row R = 0 and column C = 1:

• Rule 1: Row R = 0 and column C = 1 both have exactly three “1’s” in them.
• Rule 2: The rows that have “1’s” at column C = 1 are row 0, row 1, and row 2. These rows are exactly the same as row R = 0.
  • Total “1’s” till now = 3

Next, we consider row R = 0 and column C = 2:

• Rule 1: Row R = 0 and column C = 2 should both have exactly N number of “1’s”.
• However, this violates Rule 1 since row R = 0 has three “1’s” and column C = 2 has only one “1”.
  • Total “1’s” till now = 3 + 0

Finally, we consider row R = 0 and column C = 3:

• Rule 1: Row R = 0 and column C = 3 both have exactly N = 3 “1’s”.
• Rule 2: The rows that have “1’s” at column C = 3 are row 0, row 1, and row 2. These rows are exactly the same as row R = 0.
  • Total “1’s” till now = 3 + 0 + 3 = 6

We can apply this process for all rows and columns to determine the total count of “1’s” following the given rules.

Input: mat= [[0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 0], [0, 0, 1, 0, 0, 0]], N = 3
Output: 9

Approach: Follow the steps to solve the problem:

The approach is based on matrix traversal.

Follow the steps to solve the problem:

• Initialize auxiliary array rows[] and cols[] to track how many 1’s are in the corresponding row or column.
• Initialize a variable say, ans to store the number of 1’s that satisfy the given condition.
• Now traverse through the matrix mat[][] and check if mat[i][j]==1 then increment rows[i]++(for row) and increment cols[j]++(for column).
• Create a boolean matrix of size row*row named ‘same’ for pre-calculating the row’s equality
• Run a loop from i = 0 to i < m,
  • Run a loop from j = 0 to j < n, and check if mat[i] == mat[j], if yes then mark true for the position same[i][j]==same[j][i] in the boolean matrix
• Run a loop from i = 0 to i < m,
  • Run a loop from j = 0 to j < n,
    • check if the position of the 1 in this coordinate is the same as all rows with 1’s in column C as well as the same in row R, if yes res++
• return res

Below is the code for the above approach:

// A program to find the Number of ones
// in the binary matrix while satisfying
// some conditions
#include <bits/stdc++.h>
using namespace std;

// If the position of the 1 in this
// coordinate is the same .as all rows
// with 1's in column C as well as the
// same in row R return true else
// return false,
bool check(const vector<vector<int> >& mat, int x, int y,
           int N, const vector<int>& rows,
           const vector<int>& cols,
           vector<vector<bool> >& same)
{
    if (mat[x][y] != 1)
        return false;
    if (rows[x] != N)
        return false;
    if (cols[y] != N)
        return false;

    for (int i = 0; i < mat.size(); i++)
        if (mat[i][y] == 1 && !same[i][x])
            return false;
    return true;
}

int findNumberOfOnes(vector<vector<int> >& mat, int N)
{

    // Auxiliary row and col for tracking
    // how many B at that corresponding
    // row and col
    int R = mat.size(), C = mat[0].size();
    vector<int> rows(R, 0), cols(C, 0);

    // Traversing through the mat[][]
    // matrix. If mat[i][j]==B then
    // increment rows[i]++(for row) and
    // increment cols[j]++(for column).
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (mat[i][j] == 1)
                rows[i]++, cols[j]++;

    // Create a boolean matrix of size
    // row*row named 'same' for pre-
    // calculating the row's equality
    vector<vector<bool> > same(R, vector<bool>(R, false));
    for (int i = 0; i < R; i++)
        for (int j = i; j < R; j++)
            if (mat[i] == mat[j])
                same[i][j] = same[j][i] = true;

    int res = 0;

    // Traverse the mat[][] matrix again
    // for checking if the position of
    // the 1 in this coordinate is the
    // same as all rows with 1's in column
    // C as well as the same in row R,
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)

            // call check function if
            // returned true res++
            if (check(mat, i, j, N, rows, cols, same))
                res++;
    return res;
}

// Drivers code
int main()
{
    vector<vector<int> > mat = { { 0, 1, 0, 1, 1, 0 },
                                 { 0, 1, 0, 1, 1, 0 },
                                 { 0, 1, 0, 1, 1, 0 },
                                 { 0, 0, 1, 0, 1, 0 } };
    int N = 3;

    // Function Call
    cout << findNumberOfOnes(mat, N);
    return 0;
}

6

Time Complexity: O(R*C*(R2)), where R is the number of rows in the binary matrix and C is the number of columns in the binary matrix.
Auxiliary Space: O(R+C+R2)