Problem Statement
This problem statement contains images that may not display properly outside the applet.
There are N characters in the Ninja language. As the number of different characters can be very large, we will use numbers from 1 to N to represent the individual characters in Ninja language. The characters are numbered in alphabetical order. That is, whenever i < j, character i is earlier in the alphabet than character j. Each string in Ninja language can now be seen as a sequence of integers. When comparing two different strings of the same length, the lexicographically smaller one is the one with a smaller integer on the first place where they differ.
Ninja Ren has a string R of length N that contains each character exactly once. Then she converted the string R to the string S using the following method:
First, Ren takes her string R and writes it onto a circular piece of paper. The paper can now be cut at one of N possible positions, each time producing a different string of length N. Ren takes those N different strings and sorts them into lexicographical order (starting with the lexicographically smallest one). The string S is obtained by taking the last characters of the N sorted strings, in order. In other words, Ren takes the N cyclic rotations of R, sorts them, and then only looks at their last letters.
For example, when R is "2 4 5 1 3", S will be "5 3 1 2 4". The following picture shows how the conversion works.
You are given the int N and a int[] first. containing a prefix of the string S. More precisely, for each valid index i, element i of first is the i-th character of S. (Both indices are 0-based.)
Find the lexicographically smallest possible string S. If N is less than or equal to 50, return the entire string S. If N is greater than 50, return just the last 50 characters of S. If there is no such S, return an empty int[] instead.
There are N characters in the Ninja language. As the number of different characters can be very large, we will use numbers from 1 to N to represent the individual characters in Ninja language. The characters are numbered in alphabetical order. That is, whenever i < j, character i is earlier in the alphabet than character j. Each string in Ninja language can now be seen as a sequence of integers. When comparing two different strings of the same length, the lexicographically smaller one is the one with a smaller integer on the first place where they differ.
Ninja Ren has a string R of length N that contains each character exactly once. Then she converted the string R to the string S using the following method:
First, Ren takes her string R and writes it onto a circular piece of paper. The paper can now be cut at one of N possible positions, each time producing a different string of length N. Ren takes those N different strings and sorts them into lexicographical order (starting with the lexicographically smallest one). The string S is obtained by taking the last characters of the N sorted strings, in order. In other words, Ren takes the N cyclic rotations of R, sorts them, and then only looks at their last letters.
For example, when R is "2 4 5 1 3", S will be "5 3 1 2 4". The following picture shows how the conversion works.
You are given the int N and a int[] first. containing a prefix of the string S. More precisely, for each valid index i, element i of first is the i-th character of S. (Both indices are 0-based.)
Find the lexicographically smallest possible string S. If N is less than or equal to 50, return the entire string S. If N is greater than 50, return just the last 50 characters of S. If there is no such S, return an empty int[] instead.
Definition
- Class:
- StRings
- Method:
- getSmallest
- Parameters:
- int, int[]
- Returns:
- int[]
- Method signature:
- int[] getSmallest(int N, int[] first)
- (be sure your method is public)
Constraints
- N will be between 1 and 100,000 inclusive.
- first will contain between 1 and 50 elements, inclusive.
- Each element of first will be between 1 and N, inclusive.
- Elements of first will be pairwise distinct.
- The constraints above guarantee that the number of elements of first will be less than or equal to N.
Examples
5
{2, 4}Returns: {2, 4, 1, 5, 3 }{2, 4, 1, 5, 3} is the lexicographically smallest possible string S.5
{1}Returns: { }There is no S that starts with 1.10
{3, 8, 6}Returns: {3, 8, 6, 1, 2, 5, 4, 9, 10, 7 }100
{34, 68, 97, 87, 47, 39, 50, 59, 4, 7, 29, 91, 1, 80, 90, 95, 60, 40, 43, 73, 54, 69, 32, 31, 53, 11, 84, 3, 28, 77, 44, 86, 2, 75, 85, 52, 93, 81, 70, 89, 19, 67, 98, 100, 41, 65, 57, 27, 33, 49}Returns: {5, 6, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 30, 35, 36, 37, 38, 42, 45, 46, 48, 51, 55, 56, 58, 61, 62, 63, 64, 71, 66, 72, 74, 76, 78, 79, 82, 88, 83, 94, 96, 92, 99 }If N is greater than 50, return just the last 50 characters of S.1
{1}Returns: {1 }
Back to all problems