LCM of numbers.
There are N bandits from 1 to N. Given a permuatation of 1 to N which determines that the bandit at ith position should move to jth position. At every whistle the bandit staying on position i should run to the j-th position. Now you need to find minimum number of whistle such that each bandit is at it’s original location.
Find all independent cycle of rotation and then find the lcm of the length of each cycle.
Cycle here denotes the positions with which a bandit at position i moves to come to position i.
For example : 2 3 1 5 4 [ Sample Test Case 2 ]
Bandit at position 1, 2 and 3 come to their original position after every 3 whistles.
Bandit at position 4 and 5 come to their original position after every 2 whistles.
Finding lcm will give you the minimum whistle required so that every bandit is in their original position. Proof is left as an exercise for the reader to complete it.
Challenge 1 : Finding the cycle lengths.
Cycle length can be found simply by iterating through each cycle.Please have a look at pseudo code for more insights.
Let Visited be 0 initialized. Matching is the initial given array. for(int i=1;i<=N;i++) if( Visited[i]==0 ) length =1,s=Matching[i]; Visited[i]=1; //iterating the cycle while( s != i ) Visited[s]=1; length++; s= Matching[s];
Challenge 2 : Finding the lcm of the lengths.
Since this can be very large number , you need to be extremely careful in many languages about this because of the size limit of the data types.
So , for every length of the cycle we got , we need to separate it in terms of prime numbers alone i.e. length = p1^e1 * p2^e2 … pk^ek , where pi is prime number and ei is the maximum power of each prime number.
We need to maintain a global array of prime numbers in which we will keep the maximum value of power of every prime numbers.From this step we are finding lcm. Finally , when we have got the array , we will find the lcm by multiplying every prime number raised to it’s maximum power modulo given_mod.
let the given array be
2 3 4 1 6 7 5 9 10 11 12 8 14 13
Cycle 1 : 2 3 4 1
Cycle 2 : 6 7 5
Cycle 3 : 9 10 11 12 8
Cycle 4 : 14 13
Length of Cycles are : 4,3,5 and 2
Max_Power_Of 2 is 2
Max_Power_Of 3 is 1
Max_Power_Of 5 is 1
So the Answer is 22 * 31 * 51 = 60
I will urge the readers to figure out the error in the given pseudo code below :
Wrong_Solution ( Length L ) //given array of lengths ans = 1 for ( i = 1 ; i<=L.size() ; i = i+1 ) ans = lcm ( ans,L[i] ) if ans >= mod : ans %= mod
O(N) , you just need to find cycles in O(N) time and factorization is done in sqrt(N) time.
AUTHOR’S and TESTER’S SOLUTIONS:
Author’s solution to be uploaded soon.