Problem Statement |
| | You will be given two int[]s lows and highs describing a group of integer ranges. lows[i] and highs[i] represent the lower and upper inclusive bounds for the ith range of numbers. None of the ranges will overlap. The total group of numbers used in this problem will be the combination of the ranges given in lows and highs.
You will also be given a numeric String lexPos and a String[] retInts containing numeric Strings.
Assume you listed all
possible permutations of the given group of numbers in ascending lexicographical order (no repeated permutations). Find
the permutation A that is in position lexPos lexicographically. Return a int[] with the same
number of elements as retInts whose kth element is A[retInts[k]]. lexPos is a 0-based
index into the list of possible permutations. Each element of retInts is a 0-based index into the relevant permutation.
In a lexicographical ordering, permutations are ordered by their first
elements, with ties broken by their second elements, further ties broken by their third elements, and so forth. If
lexPos is greater than the total possible number of lexicographical orderings (without repeats) T, then use
lexPos%T instead of lexPos (% denotes mod). |
| |
Definition |
| | | Class: | PermutationValues | | Method: | getValues | | Parameters: | int[], int[], String, String[] | | Returns: | int[] | | Method signature: | int[] getValues(int[] lows, int[] highs, String lexPos, String[] retInts) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Each element of retInts and lexPos will fit in a long. |
| |
Constraints |
| - | lows will contain between 1 and 50 elements inclusive |
| - | highs will contain the same number of elements as lows |
| - | lexPos will be between 0 and (2^63)-1 inclusive |
| - | lexPos will contain only digits (0-9), will not have extra leading zeros, and will not contain whitespace |
| - | lexPos will contain between 1 and 50 characters inclusive |
| - | retInts will contain between 1 and 50 elements inclusive |
| - | Each element of lows will be between -2^31 and (2^31)-1 inclusive |
| - | Each element of highs will be between -2^31 and (2^31)-1 inclusive |
| - | Element k of lows will not be greater than element k of highs |
| - | No two ranges will overlap |
| - | Each element of retInts will contain only digits (0-9), will not have extra leading zeros, and will not contain whitespace |
| - | Each element of retInts will contain between 1 and 50 characters inclusive |
| - | Each element of retInts will be between 0 and tot-1 inclusive, where tot is the total amount of numbers in all ranges combined |
| |
Examples |
| 0) | |
| | {1} | {4} | "0" | {"0","1","2","3"} |
| Returns: { 1, 2, 3, 4 } | | The 0th permutation lexicographically is the sequence 1,2,3,4. |
|
|
| 1) | |
| | | Returns: { 3, 2, 1 } | The 6 possible permutations, in order, are :
0) 1, 2, 3
1) 1, 3, 2
2) 2, 1, 3
3) 2, 3, 1
4) 3, 1, 2
5) 3, 2, 1
lexPos is 5 so you return the 0th, 1st, and 2nd elements of permutation 5
|
|
|
| 2) | |
| | {1,16} | {5,20} | "1000000" | {"0","1","2","3","4","5","6","7","8","9","1","2","3"} |
| Returns: { 3, 18, 19, 4, 20, 2, 16, 17, 1, 5, 18, 19, 4 } | | Notice the repeated elements in retInts |
|
|
| 3) | |
| | {1} | {5} | "100000000000001" | {"0","1","2","3","4"} |
| Returns: { 2, 4, 5, 3, 1 } | |
|
| 4) | |
| | {-1000000000,500000} | {0,2000000000} | "99999999999999999" | {"2999500000","1234123","123344","9293939","2999500001","2999499950"} |
| Returns: { 1999999987, -998765877, -999876656, -990706061, 1999999982, 1999999949 } | |
|
| 5) | |
| | |
| 6) | |
| | {0,-100,101} | {99,-11,100000000} | "100000000000009" | {"4","100000087","7"} |
| Returns: { -96, 99999993, -93 } | |
|