Minimum Number Of People To Teach

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in companies
TwitterAmazon

Problem statement

Ninja has started a social networking site, Ninjas Space. There are a total of ‘N’ users and ‘M’ different types of languages on the social network in which users can communicate with each other if they know a common language. There are a total of ‘L’ friendships between users on the social network.

You have given a 2-dimensional array ‘LANGUAGES’ with ‘N’ rows and ‘M’ columns, where LANGUAGES[i][j] is equal to 1 if the user 'i+1' knows the language 'j+1'. Otherwise, LANGUAGES[i][j] is equal to 0. The friendships are given in a 2-dimensional array ‘FRIENDS’ of size ‘L’, in which FRIENDS[i] contains two users who are friends with each other on the social network. Ninja has decided to teach the same language to some users so all friends can communicate with each other. Your task is to find the minimum number of users Ninja needs to teach.

For example:

'LANGUAGES' = [[1,0,1],[0,0,1],[0,1,0]] and 'FRIENDS' =[[1,3],[2,3]], Ninja can teach the third language to the third user so all friends can communicate with each other. Hence, the answer is 1 in this case.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains three space-separated integers, 'N', M’, and ‘L’, denoting the number of rows and the number of columns in the array 'Languages', and the number of rows in the array 'Friends' respectively.

The next 'N' lines of each test case contain 'M' space-separated integers denoting the elements of the array 'LANGUAGES'.

The next 'L' lines of each test case contain two space-separated integers denoting the elements of the array ‘FRIENDS’.
Output Format: 
For each test case, return a single integer -  the minimum number of users Ninja needs to teach.
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] can only contain 2 values, i.e, 0 and 1
All tuples in 'FRIENDS' array are unique.

Time limit: 1 sec
Sample Input 1:
2
2 2 1
0 1
1 0
1 2
3 3 2   
1 1 0
0 1 0
0 1 1
1 2
2 3
Sample Output 1:
1
0
Explanation of sample input 1:
For the first test case, 
Ninja can either teach the first language to the first user or the second language to the second user so that both users can communicate with each other. Hence, the answer is 1 in this case.

For the second test case,
Users 1 and 2 can communicate with each other in the second language. Similarly, Users 2 and 3 can communicate with each other in the second language. Hence, the answer is 0 in this case.
Sample Input 2:
2
3 2 3   
1 0
0 1
0 1
1 2 
1 3
2 3
4 3 4   
1 0 0 
0 1 0 
0 0 1 
1 0 0
1 2 
1 3
2 3
3 4
Sample Output 2:
1
2
Hint

Try to think of an approach by trying each language once and finding the total number of users Ninja needs to teach.

Approaches (1)
Brute force

To obtain the total number of users Ninja needs to teach, we first need to find the users who cannot communicate with their friends on the social network. Our approach will be to maintain a set and iterate over the array 'FRIENDS', and we will check for every pair of friends whether both of them know a common language using which they can communicate with each other. If both users do not know a common language, then we will insert both users into the set. 

 

After obtaining the users, we will iterate over each language, and for each language, we will find the total number of users Ninja needs to teach if Ninja chooses that particular language. In the end, we will return the minimum number of users that Ninja needs to teach in any particular language. This approach works as Ninja teaches a common language to those users who cannot communicate with their friends.

 

Algorithm:

  • We will initialize the variable 'MINIMUM_USERS' with ‘N’, and it will store the minimum number of users Ninja needs to teach.
  • Maintain a set, which stores users who cannot communicate with their friends.
  • Iterate 'INDEX' from 0 to ‘L-1’,
    • Check if users 'FRIENDS'['INDEX'][0] and 'FRIENDS'['INDEX'][1] shares a common language.
    • If both users do not share a common language, then insert both users in the set.
  • Iterate 'INDEX' from 0 to ‘M-1’,
    • We will set the variable 'TOTAL_USERS' as 0, which will store the total number of users Ninja needs to teach if Ninja chooses 'INDEX'+1 language.
    • Iterate it over the set
      • Check if the user at it cannot speak 'INDEX'+1 language, then increment 'TOTAL_USERS' by 1.
    • If 'MINIMUM_USERS' is more than 'TOTAL_USERS', then update 'MINIMUM_USERS' with 'TOTAL_USERS'.
  • Return the variable 'MINIMUM_USERS'.
Time Complexity

O(L*M + N*M), where ‘N’ and ‘M’ is the number of rows and the number of columns in the array Languages, and ‘L’ is the number of rows in the array Friends.

 

The Time Complexity to find users who do not share a common language with their friends is O(L*M). The Time Complexity to find the language by which Ninja needs to teach the minimum number of users is O(N*M). Hence, the overall time complexity is O(L*M + N*M).

Space Complexity

O(N), where ‘N’ is the number of rows in the array Languages.

 

In the worst case, when each user has a friend with whom he cannot communicate, the number of elements in the set will be N. Hence, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Number Of People To Teach
Full screen
Console