Permutation cycles
Statement
Goal
A permutation in one-line format indicates where each item will be moved to by applying the permutation. For example, the permutation "3 1 2 5 4" moves the item at position 1 to position 3, the item at position 2 to position 1, and so forth.If we start with [1,2..n] and the given permutation is applied once, find how many more times it needs to be applied to return each item to its original position.
Image credit: https://en.wikiversity.org/wiki/Permutation_notation#/media/File:5-el_perm;_active;_only_P_as_arrow_diagram.svg
Input
Line 1: An integer N for the number of elements
Line 2: A line Perm containing N integers from 1 to N
Line 2: A line Perm containing N integers from 1 to N
Output
Line 1: N
Constraints
1 <= N <= 150
1 <= Perm[i] <= N
1 <= Perm[i] <= N
Example
Input
5 3 1 2 5 4
Output
5
Tags
Mathematics, Data Types, Number theory, Primes, Cycle detection
Difficulty
Medium
Test cases
Simple Test
Input
5
3 1 2 5 4
Output
5
Validator 1 Validator
Input
5
2 3 1 5 4
Output
5
In place Test
Input
10
1 2 3 4 5 6 7 8 9 10
Output
0
Validator 2 Validator
Input
12
1 2 3 4 5 6 7 8 9 10 11 12
Output
0
Synchronized Test
Input
8
2 1 4 3 6 7 8 5
Output
3
Validator 3 Validator
Input
9
2 3 1 9 4 5 6 7 8
Output
5
Shuffled Test
Input
8
7 1 4 2 6 8 3 5
Output
14
Validator 4 Validator
Input
8
3 6 5 8 1 4 7 2
Output
11
Big! Test
Input
100
96 55 25 78 57 40 92 38 19 59 9 20 83 71 16 27 36 13 47 67 15 8 95 33 35 88 24 99 18 86 74 91 100 44 82 62 97 66 94 34 31 17 43 64 53 12 70 23 76 73 5 7 51 87 77 1 65 45 50 37 22 68 2 30 6 32 72 46 98 84 29 11 69 75 80 26 42 89 14 49 41 79 90 63 54 52 4 58 61 48 10 60 93 85 39 56 81 28 21 3
Output
179
Validator 5 Validator
Input
100
36 24 46 54 13 15 49 21 19 60 62 78 47 80 18 38 56 85 72 83 64 91 96 77 41 86 3 11 82 20 92 100 52 26 32 31 76 4 73 74 65 12 88 94 29 58 66 93 53 95 61 57 30 5 40 97 51 50 16 23 71 87 68 7 28 90 2 89 75 84 79 27 63 42 39 25 1 48 6 59 17 14 70 67 44 98 33 8 81 34 45 69 37 22 99 55 43 35 9 10
Output
4639
Bruteforce this! Test
Input
88
2 3 4 5 1 7 8 9 10 11 12 6 14 15 16 17 18 19 20 21 22 23 13 25 26 27 28 29 30 31 32 33 34 35 36 24 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 37 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 53 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 70
Output
25865839
Validator 6 Validator
Input
100
2 3 4 5 6 7 8 9 1 11 12 13 14 15 16 17 18 19 20 10 22 23 24 25 26 27 21 29 30 31 32 33 34 35 36 37 38 39 40 28 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 41 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 60 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 76
Output
68468399
And this! Test
Input
149
16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 41 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 48 42 43 44 45 46 47 59 49 50 51 52 53 54 55 56 57 58 72 60 61 62 63 64 65 66 67 68 69 70 71 103 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 122 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 149 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
Output
6367561199
Validator 7 Validator
Input
149
32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 55 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 62 56 57 58 59 60 61 75 63 64 65 66 67 68 69 70 71 72 73 74 86 76 77 78 79 80 81 82 83 84 85 103 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 122 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 149 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
Output
6425074655
One last test... Test
Input
136
15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 42 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 91 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 123 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 136 124 125 126 127 128 129 130 131 132 133 134 135
Output
2751839
Validator 8 Validator
Input
149
44 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 50 45 46 47 48 49 77 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 130 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 142 131 132 133 134 135 136 137 138 139 140 141 149 143 144 145 146 147 148
Output
440747
Solution language
Solution
Stub generator input