Finding the Celebrity

In a function, there is one celebrity. Everyone knows the celebrity and celebrity does not know anyone. Among the other people in the function, few people know few others. You can ask only one type of question, "Do you know this person or not?". How do you find the celebrity by asking minimum no.of questions?


Answer:

Ask the first person, whether he/she knows the second person or not. If the first person knows the second person, it means, first person is not a celebrity. We don't know whether the second person is a celebrity or not. If the first person does not know the second person, it means, second person is not a celebrity, and we don't know about the first person. By asking this question, we eliminated one person.

After eliminating one person, we can ask the remaining person, whether he/she knows the third person or not. Again from the answer he/she gives, we can eliminate one of them. If we repeat the same procedure, when we ask (n-1)th question, if the reply is no, then the person whom we asked the question, is the celebrity. Otherwise, the other person is the celebrity.

Given a matrix of relationships, the following program gives the celebrity. In the following program, a[i][j] is 1, if i knows j. It is 0, if i does not know j.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
main(int argc, char **argv)
{
 int **a;
 int n, i, j, c;
 if(argc >= 3) {
  n = atoi(argv[1]);
  c = atoi(argv[2]);
 } else {
  printf("Enter the no.of people including celebrity \n");
  scanf("%d", &n);
  printf("Enter the index of the celebrity (0 to %d)\n", n-1);
  scanf("%d", &c);
 }
 if(c < 0 || c > n-1) {
  c = n-1;
 }

 if(argc >= 4) {
  srandom(atoi(argv[3]));
 } else {
  time_t time;
  localtime(&time);
  printf("Used the seed %lu\n", time);
  srandom(time);
 }

 a = (int**)calloc(n, sizeof(int*));
 if(a==NULL) {
  printf("Unable to allocate memory\n");
  exit(-5);
 }
 for(i=0; i<n; i++) {
  a[i] = (int*) calloc(n, sizeof(int));
  if(a[i] == NULL) {
   printf("Unable to allocate memory\n");
   exit(-5);
  }
 }
 for(i=0; i<n; i++) {
  for(j=0; j<n; j++) {
   if(i==j) {
    a[i][j]=1;
   } else if(i==c) {
    a[i][j]=0;
   } else if(j==c) {
    a[i][j]=1;
   } else {
    a[i][j]=random()%2;
   }
   printf("%d ", a[i][j]);
  }
  printf("\n");
 }
 printf("Random numbers are generated\n");
 printf("Celbrity is %d\n", findCelebrity(a, n));
}

int findCelebrity(int **a, int n)
{
 int i;
 int p = 0, q = 1;
 for(i=0; i<n-2; i++) {
  if(a[p][q] == 1) {
   // P is not a celebrity
   p = (p>q ? p+1 : q+1);
  } else {
   // Q is not a celebrity
   q = (p>q ? p+1 : q+1);
  }
 }
 if(a[p][q] == 1) 
  return q;
 return p;
}