Find The Celebrity In A Party Problem In C

A typical coding challenge that can be solved using algorithmic techniques and logical reasoning is known as the "Locate the Celebrity" dilemma. In this write-up, we will explore different strategies for tackling this problem using the C programming language.

Problem Statement:

A group of conditions establish a well-known individual among n attendees at an event, ranging from 0 to n-1:

• ✅ The famous person is familiar to all present at the function.
• ✅ None of the guests are acquainted with the celebrity.

A function named knows(a, b) is available, which returns true if person a knows person b and false if not. When there is a celebrity present, we need to utilize this function to determine their identity.

Approach to Solve the Problem:

Approach 1: Brute Force Approach (O(n^2) Time Complexity)

The most straightforward approach to solving this issue is to assess each individual to determine if they meet the criteria for being a celebrity by examining every other person iteratively.

#include <stdio.h>
#include <stdbool.h>
#define N 4
// Dummy implementation of the knows function
int MATRIX[N][N] = { {0, 1, 1, 1},
                      {0, 0, 1, 1},
                      {0, 0, 0, 1},
                      {0, 0, 0, 0} };
bool knows(int a, int b) 
{
    return MATRIX[a][b];
}
int findCelebrityBruteForce(int n) 
{
    for (int i = 0; i < n; i++) 
{
        bool isCelebrity = true;
        for (int j = 0; j < n; j++) 
{
            if (i != j && (knows(i, j) || !knows(j, i))) 
{
                isCelebrity = false;
                break;
            }
        }
        if (isCelebrity) return i;
    }
    return -1;
}
int main() 
{
    int celeb = findCelebrityBruteForce(N);
    if (celeb == -1) 
{
        printf("No celebrity found.\n");
    }
 else 
{
        printf("Celebrity is person %d\n", celeb);
    }
    return 0;
}

Output:

Celebrity is person 3

Approach 2: Optimized Stack-Based Approach (O(n) Time Complexity)

Instead of comparing each individual with every other individual, we can implement a stack to minimize the quantity of comparisons:

Steps:

• ✅ Push all n people onto a stack.
• ✅ Pop two people and compare them: If A knows B, then A cannot be the celebrity, so discard A. If A does not know B, then B cannot be the celebrity, so discard B.
• ✅ Repeat until one person remains.
• ✅ Verify if the remaining person is a celebrity by checking the two conditions.
• ✅ If A knows B, then A cannot be the celebrity, so discard A.
• ✅ If A does not know B, then B cannot be the celebrity, so discard B.
Example
Copy
#include <stdio.h>
#include <stdbool.h>

#define N 4

int MATRIX[N][N] = {
    {0, 1, 1, 1},
    {0, 0, 0, 0},  // Person 1 is the celebrity
    {0, 1, 0, 1},
    {0, 1, 1, 0}
};

//check if person 'a' knows person 'b'
bool knows(int a, int b) 
{
    return MATRIX[a][b];
}

// find the celebrity using stack-based approach
int findCelebrityStack(int n) 
{
    int stack[N];
    int top = -1;

    // Push all persons onto the stack
    for (int i = 0; i < n; i++) 
    {
        stack[++top] = i;
    }
    while (top > 0) 
    {
        int a = stack[top--];
        int b = stack[top--];

        if (knows(a, b)) 
        {
            // if 'a' knows 'b', 'a' cannot be a celebrity
            stack[++top] = b;
        } 
        else 
        {
            // if 'b' knows 'a' or 'b' doesn't know 'a',  'b' cannot be a celebrity
            stack[++top] = a;
        }
    }

    // The last remaining person might be a celebrity
    int candidate = stack[top];

    // Validate if the candidate is actually a celebrity
    for (int i = 0; i < n; i++) 
    {
        if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) 
        {
            return -1;  // Not a celebrity
        }
    }

    return candidate;
}

// Main function
int main() 
{
    int celeb = findCelebrityStack(N);

    if (celeb == -1) 
    {
        printf("No celebrity found.\n");
    } 
    else 
    {
        printf("Celebrity is person %d\n", celeb);
    }

    return 0;
}
Try it Yourself

Output:

Celebrity is person 1

Approach 3: Two-Pointer Approach (O(n) Time Complexity)

It is the most effective technique involving the use of two pointers:

Steps:

• ✅ Start with two pointers, one at the beginning (i=0) and one at the end (j=n-1).
• ✅ If i knows j, i cannot be a celebrity, move i forward.
• ✅ If i does not know j, j cannot be a celebrity, move j backward.
• ✅ After the loop, i is the only potential celebrity. Verify using the given conditions.
Example
Copy
int findCelebrityTwoPointer(int n) 
{
    int candidate = 0;
    for (int i = 1; i < n; i++) 
{
        if (knows(candidate, i)) 
{
            candidate = i;
        }
    }    
    // Validate the candidate
    for (int i = 0; i < n; i++) 
{
        if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) 
{
            return -1;
        }
    }    
    return candidate;
}
Try it Yourself

Complexity Analysis:

Conclusion

In summary, the "Locate the Famous Person" issue serves as a prime illustration of algorithmic issue resolution using various strategies. While the brute-force technique is straightforward, it lacks efficiency. On the other hand, both the stack-based and two-pointer methods enhance the solution, ultimately lowering the time complexity to O(n).

When getting ready for coding interviews, grasping this particular issue can enhance our ability to solve problems effectively in practical situations.