Given an integer N and the duty is to generate a permutation of the numbers in vary [1, N] such that:
- The GCD of all the weather multiplied with their place (not index) is larger than 1
- And if it’s not attainable return -1.
- If there are a number of attainable permutations, print any one among them.
Examples:
Enter: N = 8
Output: 2 1 4 3 6 5 8 7
Clarification: The elemements multiplied by their positions might be
{2*1, 1*2, 4*3, 3*4, 6*5, 5*6, 8*7, 7*8} = {2, 2, 12, 12, 30, 30, 56, 56}.
The GCD of all these numbers = 2 which is larger than 1.Enter: N = 9
Output: -1
Clarification: No permutation attainable, therefore return -1
Strategy: The concept to unravel the issue is as follows:
Attempt to make the product of place and the quantity even, then in that scenario GCD might be at the very least 2.
If there are odd variety of components then it’s not attainable, as a result of odd components are yet one more than attainable even positions.
Comply with the beneath steps to unravel the issue:
- Retailer all of the even numbers in a single vector and all of the odd numbers in one other vector.
- Whereas producing the permutation:
- Push the even quantity at even index(i.e odd place as a result of the indexing is 0 primarily based) and
- Odd quantity at odd index(i.e. even place).
Beneath is the implementation of the above method:
C++
|
|
Time Complexity: O(N)
Auxiliary Area: O(N)
