Given a optimistic integer N, the duty is to assemble a permutation from 1 to N such that absolutely the distinction of parts is in strictly growing order.
Be aware: N can’t be 0 or 1.
Examples:
Enter: N = 10
Output: 6 5 7 4 8 3 9 2 10 1
Clarification: abs(6 – 5) i.e., 1 < abs(5 – 7) i.e., 2 < abs(7 – 4) i.e., 3 …. < abs(2 – 10) i.e., 8 < abs(10 – 1) i.e., 9Enter: 3
Output: 2 3 1
Clarification: abs(2 – 3) = 1 and abs(3 – 1) = 2, 1 < 2 therefore it’s in strictly growing order.
Strategy: The issue might be solved primarily based on the next commentary:
Statement:
Let’s say, you might have the i =1 and j = N, the most important absolute distinction made is by subtracting 1 and N = (N – 1)
Subsequent Time, i increment by 1, i = 2 and j stays identical i.e., N, So, absolutely the distinction is = (N – 2).
Subsequent Time, i stays identical i.e., 2 and j decrement by 1, j = N-1, So, absolutely the distinction is = (N – 1 – 2) = (N – 3).
Subsequent Time, i increment by 1, i = 3 and j stays identical i.e., N-1, So, absolutely the distinction is = (N – 1 – 3) = (N – 4).
Subsequent Time, i stays identical i.e., 3 and j decrement by 1, j = N-2, So, absolutely the distinction is = (N – 2 – 3) = (N – 5)……Now, this manner the collection go, and eventually two situation attainable,
- When i = j + 1, [If N is odd], absolute distinction = 1
- Or, j = i + 1, [If N is even], absolute distinction = 1
So, this manner the collection change into for given N, collection = (N – 1), (N – 2), (N – 3), …. 3, 2, 1.
Comply with the beneath steps to unravel the issue:
- Initialize a pointer i = 1 and j = N.
- Declare an array of dimension N.
- Run a loop (utilizing iterator x) from 0 to N – 1.
- If x is even then set, arr[x] = i and increment i by 1.
- Else then set, arr[x] = j and decrement j by 1.
- After executing the loop, print the array in reverse order.
Under is the implementation of the above strategy:
C++
|
|
6 5 7 4 8 3 9 2 10 1
Time Complexity: O(N)
Auxiliary Area: O(N)
