We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Here's an un-clever solution. It's still linear time but comes at the cost of an extra linear amount of overhead.
The gist is that we're going to be constructing our permutation one number at a time.
For the ith number in the permutation, we can choose (-K + i), (K + i), or neither. The value we choose has to be between 1 and N, as well as not already used in our permutation. Moreover, we should choose (-K + i) over (K + i) if both work*. If we ever encounter an iteration where neither choice is possible, we can stop as no such permutation is possible. If we can choose a number in each iteration, we'll end up with the required permutation.
*We should choose (-K + i) over (K + i) because we won't be seeing this value C = (-K + i) ever again in the coming iterations. Since K is given to be positive, (-K + i) <= (K + i). As we look at the choices for future numbers in the permutation, i increases. In turn, (-K + i) and (K + i) will increase further and further away from C. So if we don't choose C = (-K + i), our "permutation" will be missing that value and won't actually be a permutation of the correct set of 1 to N.
If you think about it, this means we don't have to worry about computing the lexicographically smallest permutation. There's only ever one correct choice to be made at each iteration.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Absolute Permutation
You are viewing a single comment's thread. Return to all comments →
Here's an un-clever solution. It's still linear time but comes at the cost of an extra linear amount of overhead.
The gist is that we're going to be constructing our permutation one number at a time.
For the ith number in the permutation, we can choose (-K + i), (K + i), or neither. The value we choose has to be between 1 and N, as well as not already used in our permutation. Moreover, we should choose (-K + i) over (K + i) if both work*. If we ever encounter an iteration where neither choice is possible, we can stop as no such permutation is possible. If we can choose a number in each iteration, we'll end up with the required permutation.
*We should choose (-K + i) over (K + i) because we won't be seeing this value C = (-K + i) ever again in the coming iterations. Since K is given to be positive, (-K + i) <= (K + i). As we look at the choices for future numbers in the permutation, i increases. In turn, (-K + i) and (K + i) will increase further and further away from C. So if we don't choose C = (-K + i), our "permutation" will be missing that value and won't actually be a permutation of the correct set of 1 to N.
If you think about it, this means we don't have to worry about computing the lexicographically smallest permutation. There's only ever one correct choice to be made at each iteration.