Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Number of Connected Computers.
MEDIUM
10 mins
6 upvotes
Matrices (2D Arrays)
Graph
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Matrices (2D Arrays)
-
-
Graph
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Number of Connected Computers.

Contributed by
Deep Mavani
Medium
yellow-spark
0/80
Avg time to solve 10 mins
Success Rate 90 %
Share
6 upvotes

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, Constraints, Images )
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.
Reset Code
Full screen
Auto
copy-code
Console