The Celebrity Problem [EASY]

Company: Zoho, UHG, One97, Microsoft, Google, Flipkart, Fab, Amazon

Question: You are in a party of N people, where 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. Your task is to find the stranger (celebrity) in party.
You will be given a square matrix M where if an element of row i and column j  is set to 1 it means there is an edge from ith person to jth person. An edge represent the relation that i th person knows j th person. You need to complete the functiongetId which finds the id of the celebrity if present else return -1. The function getId takes two arguments the square matrix Mand its size n.

Input:
The first line of input contains an element T denoting the No of test cases. Then T test cases follow. Each test case consist of 2 lines. The first line of each test case contains a number denoting the size of the matrix M. Then in the next line are space separated values of the matrix M.
 
Output:
For each test case output will be the id of the celebrity if present (0 based index). Else -1 will be printed. 

Constraints:
1<=T<=60
1<=N<=40
0<=M[][]<=1

Example:
Input (To be used only for expected output) 
1
3
0 1 0 0 0 0 0 1 0

Output 
1

Explanation 
For the above test case the matrix will look like
0 1 0 
0 0 0
0 1 0
Here  the celebrity is the person with index 1 ie id 1 

Code:

class Solution

{

    // The task is to complete this function

    int getId(int M[][], int n)

    {

           int a=0;

      int b =n-1;

      while (a < b) 

        {

            if ((M[a][b]==1))

               { a++;}

            else

               { b--;}

        }

  for (int i = 0; i < n; i++) 

        {

            

            if (i != a && ((M[a][i]==0) && (M[i][a]==0)))

                {return -1;}

        }

        return a;

    }

 

    }

Execution Time: 0.19 seconds