Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:
Suppose this list is [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.
If there are multiple answers, print any of them.
Example 1:
Input: n = 3, k = 1 Output: [1, 2, 3] Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.
Example 2:
Input: n = 3, k = 2 Output: [1, 3, 2] Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
Note:
n and k are in the range 1 <= k < n <= 104.Intuition
For each permutation of , let's look at the set of differences of the adjacent elements.
Algorithm
For each permutation, we find the number of unique differences of adjacent elements. If it is the desired number, we'll return that permutation.
To enumerate each permutation without using library functions, we use a recursive algorithm, where permute is responsible for permuting the indexes of in the interval .
Complexity Analysis
Time Complexity: to generate every permutation in the outer loop, then work to check differences. In total taking time.
Space Complexity: . We use to store whether we've seen the differences, and each generated permutation has a length equal to .
Intuition
When , a valid construction is . One way to see this is, we need to have a difference of , which means we need and adjacent; then, we need a difference of , etc.
Also, when , a valid construction is . So we have a construction when is tiny, and when it is large. This leads to the idea that we can stitch together these two constructions: we can put first so that is effectively , and then finish the construction with the first method.
For example, when and , we will construct the array as . This consists of two parts: a construction of and a construction of where every element had added to it (i.e. ).
Algorithm
As before, write first. The remaining elements to be written are , and we'll write them in alternating head and tail order.
When we are writing the element from the remaining , every even is going to be chosen from the head, and will have value . Every odd is going to be chosen from the tail, and will have value .
Complexity Analysis
Time Complexity: . We are making a list of size .
Space Complexity: . Our answer has a length equal to .
Analysis written by: @awice