Minimum Number Of People To Teach

Ninja has started a social networking site called Ninjas Space. The platform consists of ‘N’ users and supports ‘M’ different languages. Users communicate if they know at least one common language. There are ‘L’ friendships among users on this network.

You are provided with a 2D array called ‘LANGUAGES’ which has ‘N’ rows and ‘M’ columns, where LANGUAGES[i][j] == 1 indicates user i+1 knows language j+1. Otherwise, it is 0. Additionally, a 2D array ‘FRIENDS’ of size ‘L’ is given, where each row represents a pair of friends. The task is to determine the minimum number of users Ninja needs to teach a common language so all friends can communicate.

Input:

The first line of input contains an integer, 'T', representing the number of test cases.
For each test case:
The first line contains three space-separated integers, 'N', 'M', and 'L'. 
Each of the next 'N' lines contains 'M' space-separated integers for the 'LANGUAGES' array.
Each of the next 'L' lines contains two space-separated integers for the 'FRIENDS' array.

Output:

For each test case, output the minimum number of users Ninja needs to teach.

Example:

'LANGUAGES' = [[1,0,1],[0,0,1],[0,1,0]], 'FRIENDS' =[[1,3],[2,3]]

Ninja can teach the third language to the third user so all friends can communicate with each other. Thus, the result is 1.

Constraints:

  • 1 <= T <= 10
  • 1 <= N <= 500
  • 1 <= M <= 500
  • 1 <= L <= 500
  • 1 <= FRIENDS[i][0], FRIENDS[i][1] <= N
  • FRIENDS[i][0] != FRIENDS[i][1]
  • LANGUAGES[i][j] values are either 0 or 1
  • All entries in 'FRIENDS' are unique

Time limit: 1 second.

AnswerBot
4mo

Determine the minimum number of users to teach a common language so all friends can communicate on a social networking site.

  • Create a graph where users are nodes and friendships are edges.

  • Find connecte...read more

Help your peers!
Select
Add answer anonymously...

Top Software Developer Interview Questions Asked at Twitter

Q. Explain the process of calling an API.
Q. How do you test the feasibility of an idea?
Q. Design a Facebook-like application.
Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2025 Info Edge (India) Ltd.

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits