Here's a question that I was reading
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 for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.
You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.
Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
Example 1:
Input: n = 2, trust = [[1,2]]
Output: 2
Example 2:
Input: n = 3, trust = [[1,3],[2,3]]
Output: 3
Example 3:
Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Here's an answer that was used to solve the question.
fun findJudge(n: Int, trust: Array<IntArray>): Int {
val arrayN = IntArray(n)
for (i in trust){
arrayN[i[0] - 1]--
arrayN[i[1] - 1]
}
for (index in arrayN.indices){
if (arrayN[index] == n - 1) return index 1
}
return -1
}
My question is the array. What exactly is being stored in "arrayN" after the first for loop? I appreciate the help.
CodePudding user response:
arrayN
is madeout to hold the number of people who trust the person at their index (where index 0 represents person 1, and the value at index 0 is the number of people who trust person 1).
So there are 2 conditions that need to be met, everyone trusts the judge and the judge trusts nobody.
The first line in the loop deals with the judge trusting nobody, as without it the judge could still trust someone with the sum of the total number of people trusting him being n-1
, satisfying the condition in the second segment. So we subtract one from this total so that no matter how many people trust this person, he'll always fall one short and can never be deemed the judge.
The second line simply adds one to whomever this person is said to trust. This makes sure that we can check that everyone trusts the judge satisfying the other condition.
Very elegant solution.