PEPART - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Ayush Nagal

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Multi-dimensional array

PROBLEM:

At 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 at the party.The task is to find the stranger(guest) at the party.
Given a square matrix M where if an element of row i and column j is set to 1 it means the ith person knows the jth person. You need to find the 1 ≤ id ≤ N of the guest if present, otherwise print −1.

EXPLANATION:

First of all, we need to find the person who doesn’t knows anyone. Then we need to check whether other people know this person or not. If yes, he is the guest, otherwise we need to search for other person.

for(i=0;i < n;i++)
{
    f = 1;
    for(j=0;j < n;j++)
    {
        if(M[i][j]==1)
        {
            f = 0;
            break;
        }
    }
    if(f==1)
    {
        cel = i;
        break;
    }
}

Using the above code, we get the person who doesn’t know anyone. Now we need to check, whether other people know this person or not.

f = 1;
for(i=0;i < n;i++)
{
    if(i==cel)
    continue;

    if(M[i][cel]!=1)
    {
        f = 0;
        return -1;
    }

}
return cel;

AUTHOR’S SOLUTION:

Author’s solution can be found here.