Advertisement
imashutosh51

The celebrity problem

Jul 31st, 2022
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. /*
  2.  
  3. Logic is :there can be only on celebrity possible,because for being another celebrity,first celebrity must know the other celebrity
  4. and if first celebrity knows the second celebrity,then first celebrity can't be celebrity because he knows someone else.
  5. so using stack,i found that one probable celebrity.
  6. */
  7. class Solution
  8. {
  9.     public:
  10.     int celebrity(vector<vector<int> >& arr, int n) {
  11.         int i=0;
  12.         stack <int> s;
  13.         while(i<n){
  14.             s.push(i);
  15.             i++;
  16.         }
  17.         int a,b;
  18.         while(s.size()>=2){  //either he knows or get known,if knows then it can be celebrity else possibility of being celeb
  19.             a=s.top();s.pop();
  20.             b=s.top();s.pop();  
  21.             if(arr[a][b]==1){  //a knows b so a can't be celebrity so b chances of being celebrity
  22.                 s.push(b);
  23.                 continue;
  24.             }
  25.             else{              //a doesn't knows b so a can be celebrity.b can't because a doesn't know b.
  26.                 s.push(a);
  27.             }
  28.         }
  29.         a=s.top();
  30.         for(i=0;i<n;i++){  //check fro probable celebrity that he doesnt; know anyone and known by everyone
  31.             if(i==a)
  32.                continue;
  33.             if(arr[a][i]==1)
  34.                 return -1;
  35.             if(arr[i][a]==0)
  36.                 return -1;
  37.         }
  38.         return a;
  39.     }
  40. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement