Grooving Monkeys – TCS CodeVita

Find the minimum number of seconds after which all monkeys return to their initial positions based on a given permutation pattern.

Understand the Problem

Problem Statement

Problem Description

There are N monkeys in a circus. 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 the dancing pattern of the 6 monkeys = {3,6,5,4,1,2}.
The value at monkeys[i], indicates the new position of the monkey who is standing at the i^th position.

The program must accept N integers representing the dancing pattern of the monkeys. The program must print the time after which all the monkeys are in the initial position for the first time.

Note: Optimize your logic to avoid Time Limit Exceed error.

Constraints

1 ≤ T ≤ 10 (Number of test cases)
1 ≤ N ≤ 10000 (Number of monkeys)
The dancing pattern is a valid permutation of integers from 1 to N
Positions are 1-indexed
Time complexity must be efficient to avoid TLE

Examples

Example 1

Input

1
6
4 3 1 5 6 2

Output

Explanation

Starting with monkeys a,b,c,d,e,f: - t=1: c,f,b,a,d,e - t=2: b,e,f,c,a,d - t=3: f,d,e,b,c,a - t=4: e,a,d,f,b,c - t=5: d,c,a,e,f,b - t=6: a,b,c,d,e,f The cycles are (1→4→5→6→2→3→1) with length 6. LCM(6) = 6.

Example 2

Input

3
10
3 6 5 7 10 4 2 8 1 9
4
4 3 2 1
7
3 6 1 4 7 5 2

Output

20
2
4

Explanation

For the first test case, cycles are (1→3→5→10→9→1) and (2→6→4→7→2) and (8→8). Lengths are 5, 4, 1. LCM(5,4,1) = 20. For the second, cycles are (1→4→1) and (2→3→2). LCM(2,2) = 2. For the third, cycles are (1→3→1) and (2→6→5→7→2) and (4→4). Lengths are 2, 4, 1. LCM(2,4,1) = 4.

Solution

#include <stdio.h>

// Function to calculate Greatest Common Divisor
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Function to calculate Least Common Multiple
long long lcm(long long a, long long b) {
    return (a / gcd(a, b)) * b;
}

int main() {
    int t;
    scanf("%d", &t);
    
    while (t--) {
        int n;
        scanf("%d", &n);
        
        int pattern[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &pattern[i]);
        }
        
        // Track visited positions
        char visited[n];
        for (int i = 0; i < n; i++) {
            visited[i] = 0;
        }
        
        long long result = 1;
        
        // Find all cycles
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // Calculate cycle length
                int cycle_length = 0;
                int current = i;
                
                while (!visited[current]) {
                    visited[current] = 1;
                    current = pattern[current] - 1; // Convert to 0-indexed
                    cycle_length++;
                }
                
                // Update result with LCM
                result = lcm(result, cycle_length);
            }
        }
        
        printf("%lld\n", result);
    }
    
    return 0;
}

Time:O(N) per test case - Each position is visited exactly once during cycle detection.

Space:O(N) - For the visited array and storing the permutation.

Approach:

The C solution implements the permutation cycle detection algorithm:

Input Reading: Reads number of test cases and for each case, reads N and the permutation array.
GCD/LCM Functions: Implements Euclidean algorithm for GCD and uses it to compute LCM efficiently.
Visited Tracking: Uses a boolean array to track which positions have been processed to avoid recounting cycles.
Cycle Detection: For each unvisited position, follows the permutation chain until returning to start, counting the length.
LCM Calculation: Maintains a running LCM of all cycle lengths found.
Output: Prints the final LCM for each test case.

Visual Explanation

Loading diagram...

All Problems