Fewest Pointer Changes to Make Every Node Good
Problem statement
There are n nodes numbered 1 to n. Every node points to exactly one node, possibly itself. You are given the array pointers, where pointers[i] is the node that node i + 1 points to.
A node is good if at least one of these holds:
- It is node
1. - It points to node
1. - It points to a good node.
In other words, a node other than node 1 is good when following the pointers from it eventually reaches node 1. Nodes that only point around a loop that never reaches node 1 are not good. Node 1 is good no matter where it points.
You may change where any node points. Return the smallest number of nodes whose pointers you must change so that every node is good.
Function
minimumChanges(pointers: int[]) → intExamples
Example 1
pointers = [1,2,3,4,5]return = 4Every node points to itself. Node 1 is good. Nodes 2, 3, 4 and 5 each only reach themselves, so each one must be changed, for example to point at node 1. The answer is 4.
Example 2
pointers = [3,1,2,5,4,4]return = 1Node 2 points to node 1, and node 3 points to node 2, so both are good. Nodes 4 and 5 point at each other, and node 6 points into that loop, so none of the three reaches node 1. Changing node 4 to point at node 1 makes node 4 good, then node 5 and node 6 through it. The answer is 1.
Example 3
pointers = [4,1,2,3]return = 0Node 4 points to 3, node 3 to 2, and node 2 to node 1, so every node reaches node 1. Node 1's own pointer does not matter. The answer is 0.
Constraints
1 <= n == pointers.length <= 5 * 10^41 <= pointers[i] <= n