[Solved] Rearrangement of Seats with Java, C++, Python

Rearrangement of Seats: There are N students in a class, sitting on chairs numbered from 1 to N.
Initially all the students are seated serially from 1 to N. Their teacher assigns them a task wherein the students are required to change their seats by following a pattern given to them in the form of an array. The student sitting on the ith seat is required to change its position to the seat number which is at ith index of pattern array.

Your task is to find and return the number of turns required for all students to change their seats as per the pattern until they reach back to their initial positions.

Note: The students will follow the pattern at least once.

Input Specification:
input1 : An integer value N representing the number of students in the class.
input2 : An integer array representing the pattern that the students will be following.

Output Specification:
Return an integer value representing the number of turns required for all students to change their seats as per the pattern until they reach back to their initial positions.

Example 1:
input1 : 5
input2 : {3,1,2,5,4}

Output : 6

Explanation:

Here N = 5 and the pattern given to us is {3,1,2,5,4}. Initially the students are seated serially therefore, the seating arrangement of the students is {1,2,3,4,5}.
After Turn 1, the positions of the students will be {2,3,1,5,4}
As the Initial positions are: {1,2,3,4,5}
1 will move to the 3rd position, 2 will move to the 1st position, 3 will move to the 2nd position, 4 will move to the 5th position and 5 will move to the 4th position. So, after turn 1 positions of the students are {2,3,1,5,4}
After Turn 2, the positions of the students will be {3,1,2,4,5}
The previous seating arrangement was {2,3,1,5,4}
So, following the pattern, 2 will move to the 3rd position, 3 will move to the 1st position, 1 will move to the 2nd position, 5 will move to 5th position, 4 will move to the 4th position. So, after turn 2 positions of the students are {3,1,2,4,5}
Following the logic :
After Turn 3, the positions of the students will be {1,2,3,5,4}
After Turn 4 , the positions of the students will be {2,3,1,4,5}
After Turn 5, the positions of the students will be {3,1,2,5,4}
After Turn 6 , the positions of the students will be {1,2,3,4,5}
As it takes 6 turns to reach their initial positions, therefore 6 is returned as the output.

Example 2:
input1 : 4
input2 : {3,4,2,1}

Output : 4

Solution

Steps:

1. Create an array initialPositions and currentPositions with seat numbers from 1 to N.
2. Initialize a variable turns to 0.
3. Create a boolean array visited of size N+1, initialized to false.
4. Repeat the following steps until currentPositions becomes equal to initialPositions:
   1. Increment turns by 1.
   2. Create a new array newPositions.
   3. For each seat in currentPositions: –
      • If the seat has not been visited: –
        • Update newPositions with the seat’s new position based on the swapping pattern. – Otherwise: –
          • Keep the seat’s current position in newPositions.
   4. If newPositions is equal to initialPositions, break the loop.
   5. Update currentPositions with newPositions.
   6. Reset visited to all false values.
5. Return the final value of turns, representing the minimum number of turns required to return to the initial seating arrangement.

public static int rearrangeSeats(int N, int[] pattern) {
    int[] initialPositions = new int[N];
    for (int i = 0; i < N; i++) {
        initialPositions[i] = i + 1;
    }

    int[] currentPositions = Arrays.copyOf(initialPositions, N);
    int turns = 0;
    boolean[] visited = new boolean[N + 1];

    while (true) {
        turns++;
        int[] newPositions = new int[N];
        for (int i = 0; i < N; i++) {
            if (!visited[currentPositions[i]]) {
                // sauravhathi
                newPositions[i] = currentPositions[pattern[i] - 1];
            } else {
                newPositions[i] = currentPositions[i];
            }
        }

        if (Arrays.equals(newPositions, initialPositions)) {
            break;
        }

        currentPositions = Arrays.copyOf(newPositions, N);
        visited = new boolean[N + 1];
    }

    return turns;
}

#include <iostream>
#include <vector>
#include <algorithm>

int rearrangeSeats(int N, vector<int>& pattern) {
    vector<int> initialPositions(N);
    for (int i = 0; i < N; i++) {
        initialPositions[i] = i + 1;
    }

    vector<int> currentPositions = initialPositions;
    int turns = 0;
    // sauravhathi
    vector<bool> visited(N + 1, false);

    while (true) {
        turns++;
        vector<int> newPositions(N);
        for (int i = 0; i < N; i++) {
            if (!visited[currentPositions[i]]) {
                newPositions[i] = currentPositions[pattern[i] - 1];
            } else {
                newPositions[i] = currentPositions[i];
            }
        }

        if (newPositions == initialPositions) {
            break;
        }

        currentPositions = newPositions;
        fill(visited.begin(), visited.end(), false);
    }

    return turns;
}

def rearrange_seats(N, pattern):
    initial_positions = list(range(1, N + 1))
    current_positions = initial_positions[:]
    turns = 0
    visited = [False] * (N + 1)
    # sauravhathi

    while True:
        turns += 1
        new_positions = [current_positions[p - 1] if not visited[current_positions[i] - 1] else current_positions[i] for i, p in enumerate(pattern)]

        if new_positions == initial_positions:
            break

        current_positions = new_positions[:]
        visited = [False] * (N + 1)

    return turns

Happy Learning – If you require any further information, feel free to contact me.