Suppose, you have N consecutive numbers. You need to arrange them in such a way that, after arranging, subtraction between any two adjacent number will not be same. Numbers at index 1 and N will be considered adjacent. And also, you must put number 1 at index 1. For example, when N=4, 1 3 (+2) 4 (+1) 2 (-2) 1 (-1)

this is a valid arrangement.

Is there any approach to find a O(N * log N) solution? Thanks in advance.