Last Updated: 26 Mar, 2021
Number of Connected Computers.
Moderate
Asked in companies
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:
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
Approaches
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.
- Iterate a nested loop ‘j’ from ‘0’ to ‘number of columns’:
- Return ‘ANS’.
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’.