The Celebrity Problem

version.cpp

// C++ program to find 
// celebrity in O(n) time 
// and O(1) extra space 
#include <bits/stdc++.h> 
using namespace std; 

// Max # of persons in the party 
#define N 8 

// Person with 2 is celebrity 
bool MATRIX[N][N] = {{0, 0, 1, 0}, 
					{0, 0, 1, 0}, 
					{0, 0, 0, 0}, 
					{0, 0, 1, 0} 
}; 

bool knows(int a, int b) 
{ 
	return MATRIX[a][b]; 
} 

// Returns id of celebrity 
int findCelebrity(int n) 
{ 
	// Initialize two pointers 
	// as two corners 
	int a = 0; 
	int b = n - 1; 

	// Keep moving while 
	// the two pointers 
	// don't become same. 
	while (a < b) 
	{ 
		if (knows(a, b)) 
			a++; 
		else
			b--; 
	} 

	// Check if a is actually 
	// a celebrity or not 
	for (int i = 0; i < n; i++) 
	{ 
		// If any person doesn't 
		// know 'a' or 'a' doesn't 
		// know any person, return -1 
		if ( (i != a) && 
				(knows(a, i) || 
				!knows(i, a)) ) 
			return -1; 
	} 

	return a; 
} 

// Driver code 
int main() 
{ 
	int n = 4; 
	int id = findCelebrity(n); 
	id == -1 ? cout << "No celebrity" : 
			cout << "Celebrity ID "
					<< id; 
	return 0; 
} 

n a party of N people, only one person is known to everyone. Such a person may be present in 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 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 we solve the problem.

The graph construction takes O(N2) time, it is similar to brute force search. In case of recursion, we reduce the problem instance by not more than one, and also combine step may examine M-1 persons (M – instance size).

We have following observation based on elimination technique (Refer Polya’s How to Solve It book).

If A knows B, then A can’t be celebrity. Discard A, and B may be celebrity.
If A doesn’t know B, then B can’t be celebrity. Discard B, and A may be celebrity.
Repeat above two steps till we left with only one person.
Ensure the remained person is celebrity. (Why do we need this step?)
We can use stack to verity celebrity.

Push all the celebrities into a stack.
Pop off top two persons from the stack, discard one person based on return status of HaveAcquaintance(A, B).
Push the remained person onto stack.
Repeat step 2 and 3 until only one person remains in the stack.
Check the remained person in stack doesn’t have acquaintance with anyone else.
We will discard N elements utmost (Why?). If the celebrity is present in the party, we will call HaveAcquaintance() 3(N-1) times. Here is code using stack.