Given an integer N, the task is to print a good permutation of first N natural numbers. Let’s denote the ith element of the permutation be pi.
A good permutation is a permutation such that for all 1 ? i ? N the following equations hold true,
- ppi = i
- pi != i
Basically above expressions mean, no value is equal to its position.
If no such good permutation exists then print -1.
Examples:
Input: N = 1
Output: -1
No good permutation exists.
Input: N = 2
Output: 2 1
Position of 2 is 1 and position of 1 is 2.
Approach: Consider permutation p such that pi = i. Actually, p is a sequence of numbers from 1 to N and ppi = i.
Now the only trick is to change the permutation to satisfy the second equation i.e. pi != i. Let’s swap every two consecutive elements. More formally, for each k: 2k ? n let’s swap p2k – 1 and p2k. It’s easy to see that the obtained permutation satisfies both the equations for every n with the only exception: when n is odd, there is no answer and we should print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print the good permutation// of first N natural numbersint printPermutation(int n){ // If n is odd if (n % 2 != 0) cout << -1; // Otherwise else for (int i = 1; i <= n / 2; i++) cout << 2 * i << " " << 2 * i - 1 << " ";}// Driver codeint main(){ int n = 4; printPermutation(n); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to print the good permutation// of first N natural numbersstatic int printPermutation(int n){ // If n is odd if (n % 2 != 0) { System.out.println("-1"); } // Otherwise else for (int i = 1; i <= n / 2; i++) { System.out.print(2 * i + " " + ((2 * i) - 1) + " "); } return n; }// Driver codepublic static void main(String []args){ int n = 4; printPermutation(n);}}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach# Function to print the good permutation# of first N natural numbersdef printPermutation(n): # If n is odd if (n % 2 != 0): print(-1); # Otherwise else: for i in range(1, (n // 2) + 1): print((2 * i), (2 * i - 1), end = " ");# Driver coden = 4;printPermutation(n);# This code is contributed by mits |
C#
// C# implementation of the approachusing System;class GFG {// Function to print the good permutation// of first N natural numbersstatic int printPermutation(int n){ // If n is odd if (n % 2 != 0) { Console.WriteLine("-1"); } // Otherwise else for (int i = 1; i <= n / 2; i++) { Console.WriteLine(2 * i + " " + ((2 * i) - 1) + " "); } return n; }// Driver codepublic static void Main(String []args){ int n = 4; printPermutation(n);}}// This code is contributed by Kirti_Mangal |
PHP
<?phP// PHP implementation of the approach// Function to print the good permutation// of first N natural numbersfunction printPermutation($n){ // If n is odd if ($n % 2 != 0) { echo("-1"); } // Otherwise else for ($i = 1; $i <= $n / 2; $i++) { echo(2 * $i . " " . ((2 * $i) - 1) . " "); } return $n;}// Driver code$n = 4;printPermutation($n);// This code contributed// by Code_Mech.?> |
Javascript
<script>// Javascript implementation of the approach// Function to print the good permutation// of first N natural numbersfunction printPermutation(n){ // If n is odd if (n % 2 != 0) document.write(-1); // Otherwise else for (let i = 1; i <= Math.floor(n / 2); i++) document.write((2 * i) + " " + ((2 * i) - 1) + " ");}// Driver code let n = 4; printPermutation(n); //This code is contributed by Manoj</script> |
2 1 4 3
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
