Number of Connected Computers.

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
7 upvotes
Asked in companies
FacebookOraclePaytm (One97 Communications Limited)

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 4
1 1 0 0
0 0 1 0
0 0 0 1
0 0 0 1
2 2
1 0
1 1 
Sample Output 1:
4
3
Explanation for Sample Output 1:
In test case 1, The computer ‘ARR[0][0]’ is a connected computer because there is a computer in its row other than itself. The computer ‘ARR[0][1]’ is a connected computer because there is a computer in its row other than itself. The computer ‘ARR[1][2]’ is not a connected computer because there is no computer in its row and column other than itself. The computer ‘ARR[3][2]’ is a connected computer because there is a computer in its column other than itself. The computer ‘ARR[3][3]’ is a connected computer because there is a computer in its column other than itself.

Therefore the answer is 4.

In test case 2, The computer ‘ARR[0][0]’ is a connected computer because there is a computer in its column other than itself. The computer ‘ARR[1][0]’ is a connected computer because there is a computer in its row and column other than itself. The computer ‘ARR[1][1]’ is a connected computer because there is a computer in its row other than itself. 

Therefore the answer is 3.
Sample Input 2:
2
2 2
1 0
0 1 
2 2
1 1
1 1
Sample Output 2:
0
4
Explanation for Sample Output 2:
In test case 1, The computer ‘ARR[0][0]’ is not a connected computer because there is no computer in its row and column other than itself. Also The computer ‘ARR[1][1]’ is not a connected computer because there is no computer in its row and column other than itself.

Therefore the answer is 0.

In test case 2, All the four computers are connected computers as each computer has other computer in its row and colum both.

Therefore the answer is 4.
Hint

Check for each computer in its row and column. 

Approaches (2)
Brute Force.

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’.
Time Complexity

O(N * M * (N + M)), Where ‘N’ is the number of rows and ‘M' is the number of columns of grid ‘ARR’.

 

Since for each computer(total ‘N’ * ‘M’ possible) in the grid, we are checking its row and column. Thus the time complexity will be O(N * M * (N + M)).

Space Complexity

O(1).

 

Since constant space is used. Thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Number of Connected Computers.
Full screen
Console