aboutsummaryrefslogtreecommitdiff
path: root/find_town_judge.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_town_judge.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'find_town_judge.c')
-rw-r--r--find_town_judge.c48
1 files changed, 48 insertions, 0 deletions
diff --git a/find_town_judge.c b/find_town_judge.c
new file mode 100644
index 0000000..2b22ce9
--- /dev/null
+++ b/find_town_judge.c
@@ -0,0 +1,48 @@
+// 997. Find the Town Judge
+#include "leetcode.h"
+
+/*
+ * in a town, there are 'n' people labeled from 1 to 'n'. there is a rumor that
+ * one of these people is secretly the town judge. if the town judge exists,
+ * then: the town judge trusts nobody. everybody (except the judge) trusts the
+ * judge. given: array 'trust' where 'trust[i]' = [ai, bi] representing the the
+ * person labeled ai trusts the person labeled bi. return label of judge, if
+ * they exist.
+ */
+
+int findJudge(int n, int **trust, int trustSize, int *trustColSize) {
+ int candidate = -1;
+ bool arr[n + 1];
+ for (int i = 0; i <= n; i++)
+ arr[i] = false;
+ for (int i = 0; i < trustSize; i++)
+ arr[trust[i][0]] = true;
+ for (int i = 1; i <= n; i++)
+ if (!arr[i]) {
+ candidate = i;
+ break;
+ }
+ if (candidate == -1)
+ return -1;
+ for (int i = 1; i <= n; i++)
+ arr[i] = false;
+ for (int i = 0; i < trustSize; i++)
+ if (trust[i][1] == candidate)
+ arr[trust[i][0]] = true;
+ bool ans = true;
+ for (int i = 1; i <= n; i++) {
+ if (i == candidate)
+ continue;
+ ans &= arr[i];
+ }
+ return ans ? candidate : -1;
+}
+
+int main() {
+ int trust1[][2] = {{1, 2}}, trustColSize1[] = {1};
+ int trust2[][2] = {{1, 3}, {2, 3}}, trustColSize2[] = {2};
+ int trust3[][2] = {{1, 3}, {2, 3}, {3, 1}}, trustColSize3[] = {3};
+ printf("%d\n", findJudge(2, trust1, 1, trustColSize1)); // expect: 2
+ printf("%d\n", findJudge(3, trust2, 2, trustColSize1)); // expect: 3
+ printf("%d\n", findJudge(3, trust3, 3, trustColSize1)); // expect: -1
+}