The K-th Odd-Even Zigzag

Hard

Call an arrangement of the numbers 1 through size (each used exactly once) a zigzag if odd and even numbers strictly alternate: no two neighbors share the same parity. Sort all zigzags lexicographically (as lists) and return the one at position rank (counting from one). If there are fewer than rank zigzags, return an empty list. The number of zigzags can be astronomically large, so enumerating them is not an option.

Example 1

size=4, rank=5 → [3, 2, 1, 4]

The valid orders, sorted: [1,2,3,4], [1,4,3,2], [2,1,4,3], [2,3,4,1], [3,2,1,4], [3,4,1,2], [4,1,2,3], [4,3,2,1]. The fifth is [3,2,1,4].

Example 2

size=3, rank=3 → []

With three numbers only [1,2,3] and [3,2,1] qualify; there is no third one, so the answer is an empty list.

Example 3

size=5, rank=1 → [1, 2, 3, 4, 5]

Constraints

1 ≤ size ≤ 100
1 ≤ rank ≤ 10¹⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Combinatorics Enumeration

Similar problems

XOR of Every Subset Easy A Fair Split of Colored Beads Hard Other Orders for the Same Search Tree Hard K-th Route in Alphabetical Order Hard Where Moss Species Meet Hard

Input

size=4, rank=5

Expected

[3, 2, 1, 4]

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.