Beginner
1. Consecutive Prime Sum2. Alpha Numeric Sorting3. Longest Progressive Sequence4. Divine Divisor5. Forest Fire6. Minimum Distance7. Saving for a rainy day8. Online Communities Even Groups9. Coin Distribution10. Bank Compare11. Counting Rock Samples12. Collecting Candies13. Game Of Primes14. Kth Largest Factor15. Jumble With Numbers16. Philand Coins17. Reverse Gear18. String Rotation19. The Vita Sum20. Mountain Peak Sequence21. LAZY STUDENT22. LOGIC PYRAMID23. Super ASCII String Checker24. Min Product Array25. String Of Brackets26. Exchange Of Digits27. Marathon Winner28. Common Steps29. Swayamvar30. Digit Pairs31. Dole Out Cadbury32. Petrol Pump33. Grooving Monkeys34. Death BattleGrooving Monkeys
LEVEL:Beginner
Description
N monkeys are invited to a party where they start dancing. They dance in a circular formation, very similar to a Gujarati Garba or a Drum Circle. The dance requires the monkeys to constantly change positions after every 1 second.
The change of position is not random & you, in the audience, observe a pattern. Monkeys are very disciplined & follow a specific pattern while dancing.
Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.
This array (1-indexed) is the dancing pattern. The value at monkeys[i], indicates the new of position of the monkey who is standing at the ith position.
Given N & the array monkeys[ ], find the time after which all monkeys are in the initial positions for the 1st time.
Input Format
First line contains single integer t, denoting the number of test cases.
Each test case is as follows -
Integer N denoting the number of monkeys.
Next line contains N integer denoting the dancing pattern array, monkeys[].
Output Format
Each line must contain a single integer T, where T is the minimum number of seconds after which all the monkeys are in their initial position.
1 6 3 6 5 4 1 2
6
1 4 4 2 1 3
3
1 3 1 2 3
1
Login to see Discussion
Approach
Step-i) create a method gcd to find the gcd of two numbers using recursion
Step-ii)create a method monkeys which takes a and n as argument
Step-iii)initialzie i to 0, res to 1 and c to 0
Step-iv)if i is less than or equal to n-1
Step-v)assign i to temp1 and 0 to c
Step-vi) if a[i]!=0
Step-vii)assign i to temp , a[i]-1 to i, 0 to a[temp] , increment c
Step-viii) follow above step till a[i] is not equal to 0
Step-ix)assign temp1 + 1 to i
Step-x)if c is not equal to 0 update res to r es*c/gcd(res,c)
Step-xi)repeat steps v to x till i is less than or equal to n-1
Step-x)in main method take the neccesary inputs and and print the output
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution