Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Logic is :there can be only on celebrity possible,because for being another celebrity,first celebrity must know the other celebrity
- and if first celebrity knows the second celebrity,then first celebrity can't be celebrity because he knows someone else.
- so using stack,i found that one probable celebrity.
- */
- class Solution
- {
- public:
- int celebrity(vector<vector<int> >& arr, int n) {
- int i=0;
- stack <int> s;
- while(i<n){
- s.push(i);
- i++;
- }
- int a,b;
- while(s.size()>=2){ //either he knows or get known,if knows then it can be celebrity else possibility of being celeb
- a=s.top();s.pop();
- b=s.top();s.pop();
- if(arr[a][b]==1){ //a knows b so a can't be celebrity so b chances of being celebrity
- s.push(b);
- continue;
- }
- else{ //a doesn't knows b so a can be celebrity.b can't because a doesn't know b.
- s.push(a);
- }
- }
- a=s.top();
- for(i=0;i<n;i++){ //check fro probable celebrity that he doesnt; know anyone and known by everyone
- if(i==a)
- continue;
- if(arr[a][i]==1)
- return -1;
- if(arr[i][a]==0)
- return -1;
- }
- return a;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement