I see there are `O(n)`

time `O(1)`

space solutions that are obviously better, but I think this is a very intuitive and interesting solution.

At first, everyone is a potential celebrity. We loop all celebs and make a check, we know that every call to `knows(a,b)`

will give us one information: either `a`

or `b`

is not a potential celebrity and we can remove him. So after `n`

checks we reduce the set size by half. So we have to loop the set `logn`

times until it's size is 1.

In the end, we have only one candidate left. We check whether he, in fact, does not know anyone and no one knows him.

```
public int findCelebrity(int n) {
Set<Integer> celeb = new HashSet<>();
for (int i=0; i < n; i++) {
celeb.add(i);
}
while (celeb.size() > 1) {
Iterator<Integer> iter = celeb.iterator();
int a = iter.next();
int b = iter.next();
if(knows(a, b)) {
celeb.remove(a);
} else {
celeb.remove(b);
}
}
int theCeleb = celeb.iterator().next();
for (int i=0; i < n; i++) {
if (i != theCeleb) {
if (!knows(i, theCeleb)) return -1;
if (knows(theCeleb, i)) return -1;
}
}
return theCeleb;
}
```