Number of Connected Computers.

Posted: 26 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given a grid ‘ARR’ of size ‘N' * M’. ‘ARR[i][j]’ is ‘1’ if the computer is present at position ‘(i,j)’ otherwise it is zero. A computer is said to be a connected computer if there is a computer in its row or column other than itself. Your task is to return the number of connected computers.

Example:

subsequence

Let’s say you have a grid [[1,0],[1,1]]. We can say the computer ‘ARR[0][0]’ is a connected computer because there is a computer in its column other than itself. We can say the computer ‘arr[1][0]’ is a connected computer because there is a computer in its row and column other than itself. We can say the computer ‘arr[1][1]’ is a connected computer because there is a computer in its row other than itself. Therefore the number of connected computers is 3.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated ‘N’ and ‘M’ representing the number of the rows and columns in ‘ARR’ respectively.

Each of the next ‘N’ lines of input contains ‘M’ single space-separated integers representing the elements of ‘ARR’.
Output Format:
For each test case, return the number of connected computers. 

Print the output of each test case in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 100
1 <= M <= 100
‘ARR[i][j]’ = 0 or 1

Where ‘ARR[i][j]’ is an element of grid ‘ARR’.  

Time Limit: 1 sec
Approach 1

In this approach, we will find if there are any other computers present in ‘i-th’ row or ‘j-th’ column for the ‘(i, j)-th’ computer.

 

The steps are as follows:

 

  • Declare ‘ANS’ and initialize it with zero.
  • We will iterate through the grid:-
  • Iterate a loop ‘i’ from ‘0’ to ‘number of rows’:
    • Iterate a nested loop ‘j’ from ‘0’ to ‘number of columns’:
      • If ‘ARR[i][j]’ is ‘1’ then this cell contains a computer. Iterate ‘i-th’ and ‘j-th’ column of the grid and if there is a computer other than at ‘ARR[i][j]’ increment ‘CTR’ by 1, where ‘CTR’ stores the number of computers in the row and column. If after iterating both ‘i-th’ row and ‘j-ith’ column ‘CTR’ is greater than ‘1’ then ‘ARR[i][j]’ is a connected computer therefore we will increment ‘ANS’ by 1.
  • Return ‘ANS’.
Try Problem