Last Updated: 17 Apr, 2021
Minimum Number Of People To Teach
Moderate
Asked in companies
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.
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
Approaches
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'.