FastPrep
Problem · Math

Permutation Operations 🌻

Learn this problem
● MediumWolverine TradingFULLTIMEOA

Problem statement

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 10^9+7.

    Function

    countOperations(p: int[]) → int

    Complete the function countOperations in the editor.

    countOperations has the following parameter:

    • int p[n]: a permutation of the integers from 1 to n

    Returns

    int: the number of operations required modulo 109 + 7

    Examples

    Example 1

    p = [1, 3, 2]return = 2
    In the above example, n = 3. Taking any arbitrary array arr = [7, 8, 9]
  • In each opteraion:
    • 1. the element at index 1 stays at index 1 2. the element at index 2 gets mapped to index 3 3. the element at index 3 gets mapped to index 2
  • After applying operation for the first time on 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

  • 1 ≤ n ≤ 105
  • 1 ≤ p[i] ≤ n
  • p contains all distint elements, the integers 1 through n

    • More Wolverine Trading problems

    drafts saved locally
    public int countOperations(int[] p) {
    // write your code here
}
    p[1, 3, 2]
    expected2
    checking account