# Java DC Solution with Explanation

• Hi, the most rated solution is brilliant. But this is a typical kind of divide&conquer problem. Here is my DC solution.

My general idea is to divide every set of people into 2 and try to "conquer". Let S denote the people set in every division.
(a) if |S|=1, return the person as candidate
(b) if |S|=2, return the one that "is known" as candidate, or -1 if they both don't know each other.
(c) if |S|>2, divide the set into 2. Check whether 2 candidates know each other, return the "known" one or -1 if they don't know each other.
(d) After all steps of DC, we get the final candidate. To check if it's a real celebrity, traverse to find whether he/she knows anyone.

``````public class Solution extends Relation {
public int findCelebrity(int n) {
// check if he/she knows nobody
int cand = find(0, n - 1);
if (cand == -1) return -1;
for (int i = 0; i < n; i++) {
if (i != cand && knows(cand, i)) return -1;
}
return cand;
}

private int find(int lo, int hi) { // find cele candidate: everybody knows
if (lo == hi) return lo;
int mi = (lo + hi) / 2;
int cand1 = find(lo, mi);
int cand2 = find(mi + 1, hi);
if (cand1 == -1 && cand2 == -1) return -1;
if (cand1 == -1) return cand2;
if (cand2 == -1) return cand1;
// if cand1 and cand2 is not -1
if (knows(cand1, cand2)) {
return cand2;
} else {
return knows(cand2, cand1) ? cand1 : -1;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.