Problem Statement
On the podium there are N positions in a row. The positions are numbered from 0 to N-1 (left to right). N dancers came onto the podium and each dancer stood on one of the numbered positions. The dancers are also numbered from 0 to N-1. For each i, the dancer currently standing on position i has the number start[i].
The dancers are now going to perform zero or more rounds of dancing. In each round, each dancer must change their position. At the end of each round, each position must be occupied by a dancer.
Find the smallest number R of rounds in which the dancers can rearrange themselves into sorted order (i.e., dancer i on position i, for each i). Find one possible dancing schedule that achieves this in exactly R rounds. Return a int[] with (R+1)*N elements: the numbers of the dancers (left to right) in the beginning, then their numbers (again, left to right) after round 1, then after round 2, and so on. Note that the first N elements of the return value are always identical to start.
If there is no solution, return an empty int[] instead.
Definition
- Class:
- ChangePositions
- Method:
- dance
- Parameters:
- int[]
- Returns:
- int[]
- Method signature:
- int[] dance(int[] start)
- (be sure your method is public)
Constraints
- N will be between 1 and 50, inclusive.
- start will have N elements.
- start will be a permutation of the numbers 0 through N-1, inclusive.
Examples
{0, 1, 2, 3}Returns: {0, 1, 2, 3 }{3, 1, 0, 2}Returns: {3, 1, 0, 2, 2, 3, 1, 0, 0, 1, 2, 3 }{2, 5, 4, 0, 3, 1}Returns: {2, 5, 4, 0, 3, 1, 0, 1, 2, 3, 4, 5 }
Back to all problems