In a party of N people, only one person is known to everyone. Such a person may be present at the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in the minimum number of questions.
We can describe the problem input as an array of numbers/characters representing persons in the party. We also have a hypothetical function HaveAcquaintance(A, B) which returns true if A knows B, false otherwise. How can the problem be solved?
Also given a list know[], where know[i] is represented in form {a, b} means person a knows person b.
Examples:
Input: know[] = {{1, 3}, {2, 3}, {4, 3}}, N = 4
Output: 2
Explanation: Person with id = 3 does not know anyone, but every other person knows him.Input: know[] = {{1, 3}, {2, 3}, {3, 2}, {4, 3}}, N = 4
Output: -1
Explanation: No celebrity is present in the party.
Approach: The naive approach and some optimized approaches are discussed in Set-1 of this problem.
Greedy Approach: It can be solved using greedy approach. The above problem can be solved by creating a vector of bool, and traversing the given matrix as follows:
- Traverse the matrix once and find the person that knows no one.
- Store this as the current celebrity. If current celebrity is no one, then return -1, else go to the next step.
- Traverse the matrix again and now check if every person at the party knows the current celebrity.
- If the current celebrity meets this criterion as well, return it as the party celebrity.
- Else return -1.
Below is the implementation of the above approach
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to find the celebrityint findPartyCelebrity(int N, vector<vector<int> >& know){ vector<bool> celebrity(N + 1, false); for (int i = 0; i < know.size(); i++) celebrity[know[i][0]] = true; int party_celebrity = -1; for (int i = 1; i <= N; i++) if (celebrity[i] == false) party_celebrity = i; celebrity.assign(N + 1, false); for (int i = 0; i < know.size(); i++) if (know[i][1] == party_celebrity) celebrity[know[i][0]] = true; for (int i = 1; i <= N; i++) if (i != party_celebrity && celebrity[i] == false) party_celebrity = -1; return party_celebrity;}// Driver codeint main(){ int N = 4; vector<vector<int> > know = { { 1, 3 }, { 2, 3 }, { 4, 3 } }; cout << findPartyCelebrity(N, know); return 0;} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Function to find the celebrity static int findPartyCelebrity(int N, int[][] know) { boolean[] celebrity = new boolean[N + 1]; for (int i = 0; i < know.length; i++) celebrity[know[i][0]] = true; int party_celebrity = -1; for (int i = 1; i <= N; i++) if (celebrity[i] == false) party_celebrity = i; celebrity = new boolean[N + 1]; for (int i = 0; i < know.length; i++) if (know[i][1] == party_celebrity) celebrity[know[i][0]] = true; for (int i = 1; i <= N; i++) if (i != party_celebrity && celebrity[i] == false) party_celebrity = -1; return party_celebrity; } // Driver code public static void main(String[] args) { int N = 4; int[][] know = { { 1, 3 }, { 2, 3 }, { 4, 3 } }; System.out.println(findPartyCelebrity(N, know)); }}// This code is contributed by Potta Lokesh |
Python3
# Python code to implement above approach# Function to find the celebritydef findPartyCelebrity(N, know): celebrity = [False] * (N + 1) for i in range(len(know)): celebrity[know[i][0]] = True party_celebrity = -1 for i in range(1, N + 1): if celebrity[i] == False: party_celebrity = i celebrity = [False] * (N + 1) for i in range(len(know)): if know[i][1] == party_celebrity: celebrity[know[i][0]] = True for i in range(1, N + 1): if i != party_celebrity and celebrity[i] == False: party_celebrity = -1 return party_celebrity# Driver codeN = 4know = [[1, 3], [2, 3], [4, 3]]print(findPartyCelebrity(N, know))# This code is contributed by gfgking |
C#
// C# code for the above approachusing System;class GFG { // Function to find the celebrity static int findPartyCelebrity(int N, int[,] know) { bool[] celebrity = new bool[N + 1]; for (int i = 0; i < know.GetLength(0); i++) celebrity[know[i, 0]] = true; int party_celebrity = -1; for (int i = 1; i <= N; i++) if (celebrity[i] == false) party_celebrity = i; for(int i = 0; i < N + 1; i++){ celebrity[i] = false; } for (int i = 0; i < know.GetLength(0); i++) if (know[i, 1] == party_celebrity) celebrity[know[i, 0]] = true; for (int i = 1; i <= N; i++) if (i != party_celebrity && celebrity[i] == false) party_celebrity = -1; return party_celebrity; } // Driver code public static void Main() { int N = 4; int[,] know = { { 1, 3 }, { 2, 3 }, { 4, 3 } }; Console.Write(findPartyCelebrity(N, know)); }}// This code is contributed by Samim Hossain Mondal |
Javascript
<script> // JavaScript code to implement above approach // Function to find the celebrity const findPartyCelebrity = (N, know) => { let celebrity = new Array(N + 1).fill(false); for (let i = 0; i < know.length; i++) celebrity[know[i][0]] = true; let party_celebrity = -1; for (let i = 1; i <= N; i++) if (celebrity[i] == false) party_celebrity = i; celebrity = new Array(N + 1).fill(false); for (let i = 0; i < know.length; i++) if (know[i][1] == party_celebrity) celebrity[know[i][0]] = true; for (let i = 1; i <= N; i++) if (i != party_celebrity && celebrity[i] == false) party_celebrity = -1; return party_celebrity; } // Driver code let N = 4; let know = [[1, 3], [2, 3], [4, 3]]; document.write(findPartyCelebrity(N, know));// This code is contributed by rakeshsahni</script> |
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
