3470. Permutations IV Hard

1/**
2 * [3470] Permutations IV
3 *
4 * Given two integers, n and k, an alternating permutation is a permutation of the first n positive integers such that no two adjacent elements are both odd or both even.
5 * Return the k-th alternating permutation sorted in lexicographical order. If there are fewer than k valid alternating permutations, return an empty list.
6 *  
7 * <strong class="example">Example 1:
8 * <div class="example-block">
9 * Input: <span class="example-io">n = 4, k = 6</span>
10 * Output: <span class="example-io">[3,4,1,2]</span>
11 * Explanation:
12 * The lexicographically-sorted alternating permutations of [1, 2, 3, 4] are:
13 * <ol>
14 * 	[1, 2, 3, 4]
15 * 	[1, 4, 3, 2]
16 * 	[2, 1, 4, 3]
17 * 	[2, 3, 4, 1]
18 * 	[3, 2, 1, 4]
19 * 	[3, 4, 1, 2] &larr; 6th permutation
20 * 	[4, 1, 2, 3]
21 * 	[4, 3, 2, 1]
22 * </ol>
23 * Since k = 6, we return [3, 4, 1, 2].
24 * </div>
25 * <strong class="example">Example 2:
26 * <div class="example-block">
27 * Input: <span class="example-io">n = 3, k = 2</span>
28 * Output: <span class="example-io">[3,2,1]</span>
29 * Explanation:
30 * The lexicographically-sorted alternating permutations of [1, 2, 3] are:
31 * <ol>
32 * 	[1, 2, 3]
33 * 	[3, 2, 1] &larr; 2nd permutation
34 * </ol>
35 * Since k = 2, we return [3, 2, 1].
36 * </div>
37 * <strong class="example">Example 3:
38 * <div class="example-block">
39 * Input: <span class="example-io">n = 2, k = 3</span>
40 * Output: <span class="example-io">[]</span>
41 * Explanation:
42 * The lexicographically-sorted alternating permutations of [1, 2] are:
43 * <ol>
44 * 	[1, 2]
45 * 	[2, 1]
46 * </ol>
47 * There are only 2 alternating permutations, but k = 3, which is out of range. Thus, we return an empty list [].
48 * </div>
49 *  
50 * Constraints:
51 * 
52 * 	1 <= n <= 100
53 * 	1 <= k <= 10^15
54 * 
55 */
56pub struct Solution {}
57
58// problem: https://leetcode.com/problems/permutations-iv/
59// discuss: https://leetcode.com/problems/permutations-iv/discuss/?currentPage=1&orderBy=most_votes&query=
60
61// submission codes start here
62
63impl Solution {
64    pub fn permute(n: i32, k: i64) -> Vec<i32> {
65        vec![]
66    }
67}
68
69// submission codes end
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_3470() {
77    }
78}
79