{"id":"49b6ca16-ff90-4b61-9194-371201e34c8d","name":"Celebrity Problem","description":"1. You are given a number n, representing the number of people in a party.\r\n2. You are given n strings of n length containing 0's and 1's\r\n3. If there is a '1' in ith row, jth spot, then person i knows about person j.\r\n4. A celebrity is defined as somebody who knows no other person than himself but everybody else knows him.\r\n5. If there is a celebrity print it's index otherwise print \"none\".\r\n\r\nNote -> There can be only one celebrity. Think why?","inputFormat":"Input is managed for you","outputFormat":"Index of celebrity or none","constraints":"1 &lt;= n &lt;= 10^4\r\ne1, e2, .. n * n elements belongs to the set (0, 1)","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\r\nusing namespace std;\r\n\r\nvoid celebPrblm(vector<string> &v, int n){\r\n stack<int> st; \r\n for(int i = 0; i < n; i++){\r\n st.push(i);\r\n }\r\n while(st.size() > 1){\r\n int a = st.top();\r\n st.pop();\r\n int b = st.top();\r\n st.pop();\r\n\r\n if(v[a][b] == '1'){\r\n st.push(b);\r\n }else{\r\n st.push(a);\r\n }\r\n }\r\n\r\n int possCel = st.top();\r\n st.pop();\r\n\r\n for(int i = 0; i < n; i++){\r\n if(i != possCel){\r\n if(v[i][possCel] == '0' || v[possCel][i] == '1'){\r\n cout << \"none\" << endl;\r\n return;\r\n }\r\n }\r\n }\r\n cout << possCel << endl;\r\n}\r\n\r\n\r\nint main(){\r\n int n;\r\n cin >> n;\r\n vector<string> s;\r\n\r\n for(int i = 0; i < n; i++){\r\n string str;\r\n cin >> str;\r\n s.push_back(str);\r\n }\r\n celebPrblm(s, n);\r\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[][] arr = new int[n][n];\r\n\r\n for (int j = 0; j < n; j++) {\r\n String line = br.readLine();\r\n for (int k = 0; k < n; k++) {\r\n arr[j][k] = line.charAt(k) - '0';\r\n }\r\n }\r\n\r\n findCelebrity(arr);\r\n }\r\n\r\n public static void findCelebrity(int[][] arr) {\r\n // if a celebrity is there print it''s index (not position), if there is not then print \"none\"\r\n Stack < Integer > st = new Stack < > ();\r\n for (int i = 0; i < arr.length; i++) {\r\n st.push(i);\r\n }\r\n\r\n while (st.size() > 1) {\r\n int i = st.pop();\r\n int j = st.pop();\r\n\r\n if (arr[i][j] == 1) {\r\n st.push(j);\r\n } else {\r\n st.push(i);\r\n }\r\n }\r\n\r\n int pot = st.pop();\r\n boolean flag = true;\r\n for (int i = 0; i < arr.length; i++) {\r\n if (i != pot) {\r\n if (arr[i][pot] == 0 || arr[pot][i] == 1) {\r\n flag = false;\r\n break;\r\n }\r\n }\r\n }\r\n\r\n if (flag) {\r\n System.out.println(pot);\r\n } else {\r\n System.out.println(\"none\");\r\n }\r\n }\r\n\r\n}"},"python":{"code":"def findCelebrity(arr):\r\n st = []\r\n for i in range(len(arr)):\r\n st.append(i)\r\n \r\n while len(st) > 1:\r\n a = st.pop()\r\n b = st.pop()\r\n\r\n if int(arr[a][b]) == 1:\r\n st.append(b)\r\n else:\r\n st.append(a)\r\n\r\n # Possible Celebrity\r\n pc = st.pop() \r\n \r\n for i in range(len(arr)):\r\n if i != pc:\r\n if int(arr[i][pc]) == 0 or int(arr[pc][i]) == 1:\r\n print(\"none\")\r\n return\r\n\r\n print(pc,end=\"\\n\")\r\n\r\n\r\n\r\nn = int(input())\r\narr = []\r\n\r\nfor i in range(n): \r\n row = input()\r\n arr.append(row)\r\n\r\nfindCelebrity(arr)"}},"points":10,"difficulty":"easy","sampleInput":"4\r\n0000\r\n1011\r\n1101\r\n1110","sampleOutput":"0","questionVideo":"https://www.youtube.com/embed/iHM1FPLGcsU","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9847c2b3-e3ad-4b1c-97d1-00206b1be68d","name":"Stacks And Queues For Beginners","slug":"stacks-and-queues-for-beginners","type":0},{"id":"6d3dd9c3-5b89-471c-8c48-ee77bfd8bb5b","name":"Celebrity Problem","slug":"celebrity-problem","type":1}],"next":{"id":"8ab14c05-b227-4b76-ae09-e801fb4e8702","name":"Celebrity Problem","type":3,"slug":"celebrity-problem"},"prev":{"id":"b476ee16-c9a1-4132-821e-2edc363c029a","name":"Prefix Evaluation and Conversion","type":3,"slug":"prefix-evaluation-and-conversion"}}}

Celebrity Problem

1. You are given a number n, representing the number of people in a party. 2. You are given n strings of n length containing 0's and 1's 3. If there is a '1' in ith row, jth spot, then person i knows about person j. 4. A celebrity is defined as somebody who knows no other person than himself but everybody else knows him. 5. If there is a celebrity print it's index otherwise print "none". Note -> There can be only one celebrity. Think why?

{"id":"49b6ca16-ff90-4b61-9194-371201e34c8d","name":"Celebrity Problem","description":"1. You are given a number n, representing the number of people in a party.\r\n2. You are given n strings of n length containing 0's and 1's\r\n3. If there is a '1' in ith row, jth spot, then person i knows about person j.\r\n4. A celebrity is defined as somebody who knows no other person than himself but everybody else knows him.\r\n5. If there is a celebrity print it's index otherwise print \"none\".\r\n\r\nNote -> There can be only one celebrity. Think why?","inputFormat":"Input is managed for you","outputFormat":"Index of celebrity or none","constraints":"1 &lt;= n &lt;= 10^4\r\ne1, e2, .. n * n elements belongs to the set (0, 1)","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\r\nusing namespace std;\r\n\r\nvoid celebPrblm(vector<string> &v, int n){\r\n stack<int> st; \r\n for(int i = 0; i < n; i++){\r\n st.push(i);\r\n }\r\n while(st.size() > 1){\r\n int a = st.top();\r\n st.pop();\r\n int b = st.top();\r\n st.pop();\r\n\r\n if(v[a][b] == '1'){\r\n st.push(b);\r\n }else{\r\n st.push(a);\r\n }\r\n }\r\n\r\n int possCel = st.top();\r\n st.pop();\r\n\r\n for(int i = 0; i < n; i++){\r\n if(i != possCel){\r\n if(v[i][possCel] == '0' || v[possCel][i] == '1'){\r\n cout << \"none\" << endl;\r\n return;\r\n }\r\n }\r\n }\r\n cout << possCel << endl;\r\n}\r\n\r\n\r\nint main(){\r\n int n;\r\n cin >> n;\r\n vector<string> s;\r\n\r\n for(int i = 0; i < n; i++){\r\n string str;\r\n cin >> str;\r\n s.push_back(str);\r\n }\r\n celebPrblm(s, n);\r\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[][] arr = new int[n][n];\r\n\r\n for (int j = 0; j < n; j++) {\r\n String line = br.readLine();\r\n for (int k = 0; k < n; k++) {\r\n arr[j][k] = line.charAt(k) - '0';\r\n }\r\n }\r\n\r\n findCelebrity(arr);\r\n }\r\n\r\n public static void findCelebrity(int[][] arr) {\r\n // if a celebrity is there print it''s index (not position), if there is not then print \"none\"\r\n Stack < Integer > st = new Stack < > ();\r\n for (int i = 0; i < arr.length; i++) {\r\n st.push(i);\r\n }\r\n\r\n while (st.size() > 1) {\r\n int i = st.pop();\r\n int j = st.pop();\r\n\r\n if (arr[i][j] == 1) {\r\n st.push(j);\r\n } else {\r\n st.push(i);\r\n }\r\n }\r\n\r\n int pot = st.pop();\r\n boolean flag = true;\r\n for (int i = 0; i < arr.length; i++) {\r\n if (i != pot) {\r\n if (arr[i][pot] == 0 || arr[pot][i] == 1) {\r\n flag = false;\r\n break;\r\n }\r\n }\r\n }\r\n\r\n if (flag) {\r\n System.out.println(pot);\r\n } else {\r\n System.out.println(\"none\");\r\n }\r\n }\r\n\r\n}"},"python":{"code":"def findCelebrity(arr):\r\n st = []\r\n for i in range(len(arr)):\r\n st.append(i)\r\n \r\n while len(st) > 1:\r\n a = st.pop()\r\n b = st.pop()\r\n\r\n if int(arr[a][b]) == 1:\r\n st.append(b)\r\n else:\r\n st.append(a)\r\n\r\n # Possible Celebrity\r\n pc = st.pop() \r\n \r\n for i in range(len(arr)):\r\n if i != pc:\r\n if int(arr[i][pc]) == 0 or int(arr[pc][i]) == 1:\r\n print(\"none\")\r\n return\r\n\r\n print(pc,end=\"\\n\")\r\n\r\n\r\n\r\nn = int(input())\r\narr = []\r\n\r\nfor i in range(n): \r\n row = input()\r\n arr.append(row)\r\n\r\nfindCelebrity(arr)"}},"points":10,"difficulty":"easy","sampleInput":"4\r\n0000\r\n1011\r\n1101\r\n1110","sampleOutput":"0","questionVideo":"https://www.youtube.com/embed/iHM1FPLGcsU","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9847c2b3-e3ad-4b1c-97d1-00206b1be68d","name":"Stacks And Queues For Beginners","slug":"stacks-and-queues-for-beginners","type":0},{"id":"6d3dd9c3-5b89-471c-8c48-ee77bfd8bb5b","name":"Celebrity Problem","slug":"celebrity-problem","type":1}],"next":{"id":"8ab14c05-b227-4b76-ae09-e801fb4e8702","name":"Celebrity Problem","type":3,"slug":"celebrity-problem"},"prev":{"id":"b476ee16-c9a1-4132-821e-2edc363c029a","name":"Prefix Evaluation and Conversion","type":3,"slug":"prefix-evaluation-and-conversion"}}}
plane

Editor

Loading...

Celebrity Problem

easy

1. You are given a number n, representing the number of people in a party. 2. You are given n strings of n length containing 0's and 1's 3. If there is a '1' in ith row, jth spot, then person i knows about person j. 4. A celebrity is defined as somebody who knows no other person than himself but everybody else knows him. 5. If there is a celebrity print it's index otherwise print "none". Note -> There can be only one celebrity. Think why?

Constraints

1 <= n <= 10^4 e1, e2, .. n * n elements belongs to the set (0, 1)

Format

Input

Input is managed for you

Output

Index of celebrity or none

Example

Sample Input

4 0000 1011 1101 1110

Sample Output

0

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode