Horje
Count number of 1's at specific position in a matrix - II

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:

C++

// CPP 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;
}

Java

// Java program to find the Number of ones
// in the binary matrix while satisfying
// some conditions
import java.util.*;
 
public class GFG {
    // 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.
    static boolean check(List<List<Integer> > mat, int x,
                         int y, int N, List<Integer> rows,
                         List<Integer> cols,
                         boolean[][] same)
    {
        if (mat.get(x).get(y) != 1)
            return false;
        if (!rows.get(x).equals(N))
            return false;
        if (!cols.get(y).equals(N))
            return false;
 
        for (int i = 0; i < mat.size(); i++)
            if (mat.get(i).get(y) == 1 && !same[i][x])
                return false;
        return true;
    }
 
    static int findNumberOfOnes(List<List<Integer> > mat,
                                int N)
    {
        int R = mat.size();
        int C = mat.get(0).size();
        List<Integer> rows
            = new ArrayList<>(Collections.nCopies(R, 0));
        List<Integer> cols
            = new ArrayList<>(Collections.nCopies(C, 0));
 
        // Traversing through the mat[][] matrix.
        // If mat[i][j] == 1, 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.get(i).get(j) == 1) {
                    rows.set(i, rows.get(i) + 1);
                    cols.set(j, cols.get(j) + 1);
                }
            }
        }
 
        // Create a boolean matrix of size row*row
        // named 'same' for pre-calculating the
        // row's equality
        boolean[][] same = new boolean[R][R];
        for (int i = 0; i < R; i++) {
            for (int j = i; j < R; j++) {
                if (mat.get(i).equals(mat.get(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,
                // increment res
                if (check(mat, i, j, N, rows, cols, same)) {
                    res++;
                }
            }
        }
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        List<List<Integer> > mat = Arrays.asList(
            Arrays.asList(0, 1, 0, 1, 1, 0),
            Arrays.asList(0, 1, 0, 1, 1, 0),
            Arrays.asList(0, 1, 0, 1, 1, 0),
            Arrays.asList(0, 0, 1, 0, 1, 0));
        int N = 3;
 
        // Function Call
        System.out.println(findNumberOfOnes(mat, N));
    }
}
 
// This code is contributed by Susobhan Akhuli

Python3

#A program to find the Number of ones
# in the binary matrix while satisfying
#some conditions
 
# 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,
 
def check(mat, x, y, N, rows, cols, same):
    if mat[x][y] != 1:
        return False
    if rows[x] != N:
        return False
    if cols[y] != N:
        return False
 
    for i in range(len(mat)):
        if mat[i][y] == 1 and not same[i][x]:
            return False
    return True
 
def findNumberOfOnes(mat, N):
    R = len(mat)
    C = len(mat[0])
    rows = [0] * R
    cols = [0] * C
 
    # Traversing through the mat[][] matrix.
    # If mat[i][j] == 1, then increment rows[i] (for row)
    # and increment cols[j] (for column).
    for i in range(R):
        for j in range(C):
            if mat[i][j] == 1:
                rows[i] += 1
                cols[j] += 1
 
    # Create a boolean matrix of size R x R named 'same'
    # for pre-calculating the row's equality
    same = [[False] * R for _ in range(R)]
    for i in range(R):
        for j in range(i, R):
            if mat[i] == mat[j]:
                same[i][j] = same[j][i] = True
 
    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 i in range(R):
        for j in range(C):
            # Call the check function and if it returns True, increment res
            if check(mat, i, j, N, rows, cols, same):
                res += 1
    return res
 
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
 
# Function call
print(findNumberOfOnes(mat, N))

C#

// C# program to find the Number of ones
// in the binary matrix while satisfying
// some conditions
using System;
using System.Collections.Generic;
using System.Linq;
 
public class GFG {
    // 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.
    static bool Check(List<List<int> > mat, int x, int y,
                      int N, List<int> rows, List<int> cols,
                      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.Count; i++)
            if (mat[i][y] == 1 && !same[i, x])
                return false;
        return true;
    }
 
    static int FindNumberOfOnes(List<List<int> > mat, int N)
    {
        int R = mat.Count;
        int C = mat[0].Count;
        List<int> rows
            = new List<int>(Enumerable.Repeat(0, R));
        List<int> cols
            = new List<int>(Enumerable.Repeat(0, C));
 
        // Traversing through the mat[,] matrix.
        // If mat[i,j] == 1, 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
        bool[, ] same = new bool[R, R];
        for (int i = 0; i < R; i++) {
            for (int j = i; j < R; j++) {
                if (mat[i].SequenceEqual(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,
                // increment res
                if (Check(mat, i, j, N, rows, cols, same)) {
                    res++;
                }
            }
        }
        return res;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        List<List<int> > mat = new List<List<int> >{
            new List<int>{ 0, 1, 0, 1, 1, 0 },
            new List<int>{ 0, 1, 0, 1, 1, 0 },
            new List<int>{ 0, 1, 0, 1, 1, 0 },
            new List<int>{ 0, 0, 1, 0, 1, 0 }
        };
        int N = 3;
 
        // Function Call
        Console.WriteLine(FindNumberOfOnes(mat, N));
    }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

// JavaScript program to find the Number of ones
// in the binary matrix while satisfying
// some conditions
 
// Function to check if the position of 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.
function check(mat, x, y, N, rows, cols, same) {
    if (mat[x][y] !== 1) return false;
    if (rows[x] !== N) return false;
    if (cols[y] !== N) return false;
 
    for (let i = 0; i < mat.length; i++) {
        if (mat[i][y] === 1 && !same[i][x]) {
            return false;
        }
    }
    return true;
}
 
// Function to find the number of ones in a binary matrix
// while satisfying certain conditions
function findNumberOfOnes(mat, N) {
    const R = mat.length;
    const C = mat[0].length;
 
    // Arrays to track the number of 1's in rows and columns
    const rows = new Array(R).fill(0);
    const cols = new Array(C).fill(0);
 
    // Traversing through the matrix mat[][].
    // If mat[i][j] == 1, increment rows[i] (for row) and cols[j] (for column).
    for (let i = 0; i < R; i++) {
        for (let j = 0; j < C; j++) {
            if (mat[i][j] === 1) {
                rows[i]++;
                cols[j]++;
            }
        }
    }
 
    // Create a boolean matrix named 'same' of size row * row
    // for pre-calculating the row's equality
    const same = new Array(R).fill(false).map(() => new Array(R).fill(false));
    for (let i = 0; i < R; i++) {
        for (let j = i; j < R; j++) {
            if (JSON.stringify(mat[i]) === JSON.stringify(mat[j])) {
                same[i][j] = same[j][i] = true;
            }
        }
    }
 
    let res = 0;
 
    // Traverse the matrix mat[][] again
    // to check if the position of 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 (let i = 0; i < R; i++) {
        for (let j = 0; j < C; j++) {
            // Call the check function, if it returns true, increment res
            if (check(mat, i, j, N, rows, cols, same)) {
                res++;
            }
        }
    }
 
    return res;
}
 
// Driver code
const 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]
];
const N = 3;
 
// Function Call
console.log(findNumberOfOnes(mat, N));

Output

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)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Introduction to Barret Reduction Algorithm Introduction to Barret Reduction Algorithm
Lexicographically largest permutation transformation Lexicographically largest permutation transformation
Find minimum difference and maximum difference in given String Find minimum difference and maximum difference in given String
Maximum Coverage Problem Maximum Coverage Problem
Time and Space Complexity Analysis of Tree Traversal Algorithms Time and Space Complexity Analysis of Tree Traversal Algorithms

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje