The simple, obvious, inefficient way to solve this is to call next_permutation() k times. But that results in O(n!), which is slow. It is also possible in O(n) time, which relies on cutting through the problem space for each digit. So when k=4, on an n=3 problem, we know that the first digit will appear twice as 1, twice as 2 and twice as 3. We know that k=4 lands on the middle third of the problem space, so the first digit must be 2. We can progress like this through the rest of the digits. It is quite confusing to code. I found I had to plan it all out with formulas before (see whiteboard).
-
Recent Posts
Recent Comments
Archives
Categories
Meta