Problem Brief
Minimum Number of Permutation Operations 👑
OA
A permutation of n numbers is a sequence where each number from 1 to n appears exactly once. For a given permutation p and any arbitrary array arr, a permutation operation is defined as
For each index i (1 ≤ i ≤ n) temp_arr[i] = arr[p[i]]
arr = temp_arr
Given a permutation p of n numbers, start with any arbitrary array arr of n distinct elements and find out the minimum number of permutation operations (at least 1) needed in order to reach the original array. Since the answer can be quite large, return the answer modulo (109 + 7)
1Example 1
Input
p = [1, 3, 2]
Output
2
Explanation
In the above example, the element at index 1 stays at index 1
the element at index 2 gets mapped to index 3
the element at index 3 gets mapped to index 2
After applying operation for the first time on
n = 3. Taking any arbitrary array arr = [7, 8, 9]
In each operation:
arr, the resulting array is [7, 9, 8].
After applying operation for the second time the resulting array is [7, 8, 9].
After 2 operations we get back to the original array, hence we return 2 as the answer.Constraints
Limits and guarantees your solution can rely on.
1 ≤ n ≤ 1051 ≤ p[i] ≤ np contains all distinct elements, the integers 1 through n