-
Notifications
You must be signed in to change notification settings - Fork 130
/
Find the Celebrity.js
51 lines (43 loc) · 1.27 KB
/
Find the Celebrity.js
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
51
/**
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
*/
/**
* Definition for knows()
*
* @param {integer} person a
* @param {integer} person b
* @return {boolean} whether a knows b
* knows = function(a, b) {
* ...
* };
*/
/**
* @param {function} knows()
* @return {function}
*/
var solution = function(knows) {
/**
* @param {integer} n Total people
* @return {integer} The celebrity
*/
return function(n) {
let candidate = 0;
for (let i = 1; i < n; i++) {
// if candidate know i, then swap
if (knows(candidate, i)) {
candidate = i;
}
}
// check if a candidate if valid
for (let i = 0; i < n; i++) {
if (i !== candidate && (!knows(i, candidate) || knows(candidate, i))) {
return -1;
}
}
return candidate;
};
};