Number of Connected Computers.

PROBLEM STATEMENT

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

Approach 2

In this approach we simply optimize the approach-1, We will maintain two auxiliary arrays/lists ‘COLUMNCTR’ of size ‘M' and ‘ROWCTR’ of size ‘N’. ‘COLUMNCTR[j]’ stores the number of computers in ‘j-th’ column. ‘ROWCTR[i]’ stores the number of computers in the ‘i-th’ row. if ‘ARR[i][j]' ==1, then we don’t need to iterate column/row multiple times to check if there is a computer.

The steps are as follows:

For computing ‘COLUMNCTR[j]’ we will do as follows:-
- Initialize ‘COLUMNCTR[j]’ with 0.
- Iterate through all the rows from ‘0’ to ‘N' - 1 and add ‘ARR[i][j]’ to ‘COLUMNCTR[j]’.
For computing ‘ROWCTR[i]’ we will do as follows:-
- Initialize ‘ROWCTR[i]’ with 0.
- Iterate through all the columns from ‘0’ to ‘M' - 1 and add ‘ARR[i][j]’ to ‘ROWCTR[i]’.
Declare ‘ANS’ and initialize it with zero.
We will iterate through the grid:-
- If ‘ARR[i][j]’ is ‘1’ then this cell contains a computer. If ‘COLUMNCTR[j]’ or ‘ROWCTR[i]’ is greater than ‘1’ then there is at least one computer that has the same row or column as ‘ARR[i][j]’.Therefore ‘ARR[i][j]’ is a connected computer, therefore, we will increment ‘ANS’ by 1.
Return ‘ANS’.

Try Problem