Given an integer N and two arrays A[][], representing the set of languages a person knows, and B[][], consisting of M pairs of friendships, the task is to find the minimum number of persons to be taught a single language so that every pair of friends can communicate with each other.
Examples:
Input: N = 2, A[][] = {{1}, {2}, {1, 2}}, B[][] = {{1, 2}, {1, 3}, {2, 3}}
Output: 1
Explanation:
One possible way is to teach the 1st person the language 2.
Another possible way is to teach the 2nd person the language 1.
Therefore, the minimum number of languages required to be taught is 1.Input: N = 4, A[][] = {{2}, {1, 4}, {1, 2}, {3, 4}}, B[][] = {{1, 4}, {1, 2}, {3, 4}, {2, 3}}
Output: 2
Explanation:
One of the possible way is to teach the 1st person the language 3 or 4 and the 3rd person the language 3 or 4.
Therefore, the minimum number of languages required to be taught is 2.
Approach: The given problem can be solved using a Set and Map data structure to solve the given problem.
Follow the steps below to solve the problem:
- Define a function, say Check(A[], B[]), to check if any common element is present in the two sorted arrays or not:
- Define two variables, say P1 and P2 to store the pointers.
- Iterate while P1 < M and P2 < N. If A[P1] is equal to B[P2], then return true. Otherwise, if A[P1] < B[P2], increment P1 by one. Otherwise, if A[P1] > B[P2], increment P2 by 1.
- If none of the above cases satisfy, then return false.
- Initialize a set<int>, say S, and a map<int, int>, say mp, to store all the people who cannot communicate with their friends and count of people who know a particular language.
- Initialize a variable, say result, to store the count of persons to be taught.
- Traverse the array B[][] and insert the pair of people if there is no common language between them by calling the function Check(B[i][0], B[i][1]).
- Traverse the set S of the languages a person knows and increment the count of that language in the Map mp.
- Traverse the map<int, int> mp and update result as result = min(S.size() – it.second, result).
- Finally, after completing the above steps, print the result.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Function to check if there// exists any common languagebool check(vector<int>& a, vector<int>& b){ // Stores the size of array a[] int M = a.size(); // Stores the size of array b[] int N = b.size(); // Pointers int p1 = 0, p2 = 0; // Iterate while p1 < M and p2 < N while (p1 < M && p2 < N) { if (a[p1] < b[p2]) p1++; else if (a[p1] > b[p2]) p2++; else return true; } return false;}// Function to count the minimum number// of people required to be teachedint minimumTeachings( int N, vector<vector<int> >& languages, vector<vector<int> > friendships){ // Stores the size of array A[][] int m = languages.size(); // Stores the size of array B[][] int t = friendships.size(); // Stores all the persons with no // common languages with their friends unordered_set<int> total; // Stores count of languages unordered_map<int, int> overall; // Sort all the languages of // a person in ascending order for (int i = 0; i < m; i++) sort(languages[i].begin(), languages[i].end()); // Traverse the array B[][] for (int i = 0; i < t; i++) { // Check if there is no common // language between two friends if (!check(languages[friendships[i][0] - 1], languages[friendships[i][1] - 1])) { // Insert the persons in the Set total.insert(friendships[i][0]); total.insert(friendships[i][1]); } } // Stores the size of the Set int s = total.size(); // Stores the count of // minimum persons to teach int result = s; // Traverse the set total for (auto p : total) { // Traverse A[p - 1] for (int i = 0; i < languages[p - 1].size(); i++) // Increment count of languages by one overall[languages[p - 1][i]]++; } // Traverse the map for (auto c : overall) // Update result result = min(result, s - c.second); // Return the result return result;}// Driver Codeint main(){ int N = 3; vector<vector<int> > A = { { 1 }, { 1, 3 }, { 1, 2 }, { 3 } }; vector<vector<int> > B = { { 1, 4 }, { 1, 2 }, { 3, 4 }, { 2, 3 } }; cout << minimumTeachings(N, A, B) << endl; return 0;} |
Java
// Java implementation of// the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to check if there// exists any common languagestatic boolean check(int a[], int b[]){ // Stores the size of array a[] int M = a.length; // Stores the size of array b[] int N = b.length; // Pointers int p1 = 0, p2 = 0; // Iterate while p1 < M and p2 < N while (p1 < M && p2 < N) { if (a[p1] < b[p2]) p1++; else if (a[p1] > b[p2]) p2++; else return true; } return false;}// Function to count the minimum number// of people required to be teachedstatic int minimumTeachings(int N, int languages[][], int friendships[][]){ // Stores the size of array A[][] int m = languages.length; // Stores the size of array B[][] int t = friendships.length; // Stores all the persons with no // common languages with their friends HashSet<Integer> total = new HashSet<>(); // Stores count of languages HashMap<Integer, Integer> overall = new HashMap<>(); // Sort all the languages of // a person in ascending order for(int i = 0; i < m; i++) Arrays.sort(languages[i]); // Traverse the array B[][] for(int i = 0; i < t; i++) { // Check if there is no common // language between two friends if (!check(languages[friendships[i][0] - 1], languages[friendships[i][1] - 1])) { // Insert the persons in the Set total.add(friendships[i][0]); total.add(friendships[i][1]); } } // Stores the size of the Set int s = total.size(); // Stores the count of // minimum persons to teach int result = s; // Traverse the set total for(int p : total) { // Traverse A[p - 1] for(int i = 0; i < languages[p - 1].length; i++) // Increment count of languages by one overall.put(languages[p - 1][i], overall.getOrDefault( languages[p - 1][i], 0) + 1); } // Traverse the map for(int k : overall.keySet()) // Update result result = Math.min(result, s - overall.get(k)); // Return the result return result;}// Driver Codepublic static void main(String[] args){ int N = 3; int A[][] = { { 1 }, { 1, 3 }, { 1, 2 }, { 3 } }; int B[][] = { { 1, 4 }, { 1, 2 }, { 3, 4 }, { 2, 3 } }; System.out.println(minimumTeachings(N, A, B));}}// This code is contributed by Kingash |
Python3
# Python3 implementation of# the above approach# Function to check if there# exists any common languagedef check(a, b): # Stores the size of array a[] M = len(a) # Stores the size of array b[] N = len(b) # Pointers p1 = 0 p2 = 0 # Iterate while p1 < M and p2 < N while(p1 < M and p2 < N): if (a[p1] < b[p2]): p1 += 1 elif(a[p1] > b[p2]): p2 += 1 else: return True return False# Function to count the minimum number# of people required to be teacheddef minimumTeachings(N, languages, friendships): # Stores the size of array A[][] m = len(languages) # Stores the size of array B[][] t = len(friendships) # Stores all the persons with no # common languages with their friends total = set() # Stores count of languages overall = {} # Sort all the languages of # a person in ascending order for i in range(m): languages[i].sort(reverse=False) # Traverse the array B[][] for i in range(t): # Check if there is no common # language between two friends if(check(languages[friendships[i][0] - 1], languages[friendships[i][1] - 1])==False): # Insert the persons in the Set total.add(friendships[i][0]) total.add(friendships[i][1]) # Stores the size of the Set s = len(total) # Stores the count of # minimum persons to teach result = s # Traverse the set total for p in total: # Traverse A[p - 1] for i in range(len(languages[p - 1])): # Increment count of languages by one if languages[p - 1][i] in overall: overall[languages[p - 1][i]] += 1 else: overall[languages[p - 1][i]] = 1 # Traverse the map for keys,value in overall.items(): # Update result result = min(result, s - value) # Return the result return result# Driver Codeif __name__ == '__main__': N = 3 A = [[1],[1, 3],[1, 2],[3]] B = [[1, 4],[1, 2],[3, 4],[2, 3]] print(minimumTeachings(N, A, B)) # This code is contributed by ipg2016107. |
C#
// C# implementation of// the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if there // exists any common language static bool check(int[] a, int[] b) { // Stores the size of array a[] int M = a.Length; // Stores the size of array b[] int N = b.Length; // Pointers int p1 = 0, p2 = 0; // Iterate while p1 < M and p2 < N while (p1 < M && p2 < N) { if (a[p1] < b[p2]) p1++; else if (a[p1] > b[p2]) p2++; else return true; } return false; } // Function to count the minimum number // of people required to be teached static int minimumTeachings(int N, int[,] languages, int[,] friendships) { // Stores the size of array A[][] int m = languages.Length; int[] arr1 = {1,2,3}; // Stores the size of array B[][] int t = friendships.Length; int[] arr2 = {1,2,3}; // Stores all the persons with no // common languages with their friends HashSet<int> total = new HashSet<int>(); // Stores count of languages Dictionary<int, int> overall = new Dictionary<int, int>(); // Sort all the languages of // a person in ascending order for(int i = 0; i < m; i++) Array.Sort(arr1); // Traverse the array B[][] for(int i = 0; i < t; i++) { // Check if there is no common // language between two friends if (!check(arr1,arr2)) { // Insert the persons in the Set total.Add(friendships[i,0]); total.Add(friendships[i,1]); } } // Stores the size of the Set int s = total.Count; // Stores the count of // minimum persons to teach int result = s+1; // Traverse the set total foreach(int p in total) { // Traverse A[p - 1] for(int i = 0; i < languages.GetLength(1); i++) // Increment count of languages by one overall[languages[p - 1,i]]+=1; } // Traverse the map foreach(KeyValuePair<int, int> k in overall) { result = Math.Min(result, s - k.Value); } // Return the result return result; } static void Main() { int N = 3; int[,] A = { { 1, 0 }, { 1, 3 }, { 1, 2 }, { 3, 0 } }; int[,] B = { { 1, 4 }, { 1, 2 }, { 3, 4 }, { 2, 3 } }; Console.Write(minimumTeachings(N, A, B)); }} |
Javascript
<script>// Javascript implementation of// the above approach// Function to check if there// exists any common languagefunction check(a, b){ // Stores the size of array a[] let M = a.length; // Stores the size of array b[] let N = b.length; // Pointers let p1 = 0, p2 = 0; // Iterate while p1 < M and p2 < N while (p1 < M && p2 < N) { if (a[p1] < b[p2]) p1++; else if (a[p1] > b[p2]) p2++; else return true; } return false;}// Function to count the minimum number// of people required to be teachedfunction minimumTeachings(N, languages, friendships) { // Stores the size of array A[][] let m = languages.length; // Stores the size of array B[][] let t = friendships.length; // Stores all the persons with no // common languages with their friends let total = new Set(); // Stores count of languages let overall = new Map(); // Sort all the languages of // a person in ascending order for(let i = 0; i < m; i++) languages[i].sort((a, b) => a - b); // Traverse the array B[][] for(let i = 0; i < t; i++) { // Check if there is no common // language between two friends if (!check(languages[friendships[i][0] - 1], languages[friendships[i][1] - 1])) { // Insert the persons in the Set total.add(friendships[i][0]); total.add(friendships[i][1]); } } // Stores the size of the Set let s = total.size; // Stores the count of // minimum persons to teach let result = s; // Traverse the set total for(let p of total) { // Traverse A[p - 1] for(let i = 0; i < languages[p - 1].length; i++) { // Increment count of languages by one if (overall.has(languages[p - 1][i])) { overall.set(languages[p - 1][i], overall.get(languages[p - 1][i]) + 1) } else { overall.set(languages[p - 1][i], 1) } } } // Traverse the map for(let c of overall) // Update result result = Math.min(result, s - c[1]); // Return the result return result;}// Driver Codelet N = 3;let A = [ [ 1 ], [ 1, 3 ], [ 1, 2 ], [ 3 ] ];let B = [ [ 1, 4 ], [ 1, 2 ], [ 3, 4 ], [ 2, 3 ] ];document.write(minimumTeachings(N, A, B) + "<br>");// This code is contributed by _saurabh_jaiswal</script> |
Output:
1
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
