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
\nFor each permutation of , let\'s look at the set of differences of the adjacent elements.
\nAlgorithm
\nFor each permutation, we find the number of unique differences of adjacent elements. If it is the desired number, we\'ll return that permutation.
\nTo 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
\nTime Complexity: to generate every permutation in the outer loop, then work to check differences. In total taking time.
\nSpace Complexity: . We use to store whether we\'ve seen the differences, and each generated permutation has a length equal to .
\nIntuition
\nWhen , 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.
\nAlso, 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.
\nFor 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. ).
\nAlgorithm
\nAs before, write first. The remaining elements to be written are , and we\'ll write them in alternating head and tail order.
\nWhen 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 .
\n\nComplexity Analysis
\nTime Complexity: . We are making a list of size .
\nSpace Complexity: . Our answer has a length equal to .
\nAnalysis written by: @awice
\n