Python_Programs/thecelebrityproblem.py at main · MayankVerma105/Python_Programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
N = 8

Matrix = [[0, 0, 1, 0],
          [0, 0, 1, 0],
          [0, 0, 0, 0],
          [0, 0, 1, 0]]

def knows(a, b):

    return Matrix[a][b]

def findCelebrity(n):
    s = []
    for i in range(n):
        s.append(i)

    A = s.pop()
    B = s.pop()

    while (len(s)> 1):
        if (knows(A,B)):
            A = s.pop()
        else:
            B = s.pop()

    if (len(s) == 0):
        return -1

    C = s.pop()

    if (knows(C, B)):
        C = B

    if (knows(C, A)):
        C = A

    for i in range(n):
        if ((i != C) and (knows(C,i) or not knows(i, C))):
            return -1
    return C

#Driver Code
if __name__ == '__main__':
    n = 4
    id_ = findCelebrity(n)

    if id_ == -1:
        print("No celebrity")
    else:
      print("Celebrity ID ", id_)