Given an integer N, the task is to construct a permutation from 1 to N where no adjacent elements have difference as 1. If there is no such permutation, print -1.
Permutation from 1 to N has all the numbers from 1 to N present exactly once.
Examples:
Input: N = 5
Output: 4 2 5 3 1
Explanation: As for N = 5, [ 4 2 5 3 1 ] is the only permutation where the difference between the adjacent elements is not 1.Input: N = 3
Output: -1
Approach: The problem can be solved based on the following idea:
- Difference between any two even number is more than 1 and similarly, for all odd elements their difference is more than 1
- So, print all the even numbers first followed by the odd numbers.
Follow the steps mentioned below to implement the above approach:
- If N is less than or equal to 3, then no such permutation is possible.
- If N is even, print all even numbers from 2 to N firstly, and then all odds from 1 to N – 1 print all odd numbers.
- If the N is odd, then print all even numbers from 2 to N – 1 and then all odd numbers from 1 to N.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the permutation// which satisfies the given conditionvector<int> permutation(int n){ vector<int> ans; if (n <= 3) { ans.push_back(-1); } // If n is even if (n % 2 == 0) { for (int i = 2; i <= n; i += 2) { ans.push_back(i); } for (int i = 1; i < n; i += 2) { ans.push_back(i); } } // If n is odd else { for (int i = 2; i <= n - 1; i += 2) { ans.push_back(i); } for (int j = 1; j <= n; j += 2) { ans.push_back(j); } } return ans;}// Driver Codeint main(){ int N = 5; vector<int> ans = permutation(N); for (int x : ans) cout << x << " "; return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG { // Function to find the permutation // which satisfies the given condition static List<Integer> permutation(int n) { List<Integer> ans = new ArrayList<>(); if (n <= 3) { ans.add(-1); } // If n is even if (n % 2 == 0) { for (int i = 2; i <= n; i += 2) { ans.add(i); } for (int i = 1; i < n; i += 2) { ans.add(i); } } // If n is odd else { for (int i = 2; i <= n - 1; i += 2) { ans.add(i); } for (int j = 1; j <= n; j += 2) { ans.add(j); } } return ans; } // Driver Code public static void main (String[] args) { int N = 5; List<Integer> ans = permutation(N); for (Integer x : ans) System.out.print(x + " "); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python program to generate permutation of 1 to n # with no adjacent element difference as 1def permutation(n): # for storing the resultant permutations ans = [] if n <= 3: ans.append(-1) # if n is even if n % 2 == 0: i = 0 while i <= n: ans.append(i) i += 2 i = 1 while i < n: ans.append(i) i += 2 # if n is odd else: i = 2 while i <= n-1: ans.append(i) i += 2 j = 1 while j <= n: ans.append(j) j += 2 return ans# Driver Codeif __name__ == '__main__': n = 5 ans = permutation(n) for i in ans: print(i, end=" ") # This code is contributed by Amnindersingh1414. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to find the permutation // which satisfies the given condition static List<int> permutation(int n) { List<int> ans = new List<int>(); if (n <= 3) { ans.Add(-1); } // If n is even if (n % 2 == 0) { for (int i = 2; i <= n; i += 2) { ans.Add(i); } for (int i = 1; i < n; i += 2) { ans.Add(i); } } // If n is odd else { for (int i = 2; i <= n - 1; i += 2) { ans.Add(i); } for (int j = 1; j <= n; j += 2) { ans.Add(j); } } return ans; } // Driver Code public static void Main(String[] args) { int N = 5; List<int> ans = permutation(N); foreach (int x in ans) Console.Write(x + " "); }}// This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript code for the above approach// Function to find the permutation// which satisfies the given conditionfunction permutation(n){ let ans=[]; if (n <= 3) { ans.push(-1); } // If n is even if (n % 2 == 0) { for (let i = 2; i <= n; i += 2) { ans.push(i); } for (let i = 1; i < n; i += 2) { ans.push(i); } } // If n is odd else { for (let i = 2; i <= n - 1; i += 2) { ans.push(i); } for (let j = 1; j <= n; j += 2) { ans.push(j); } } return ans;}// Driver Code let N = 5; let ans = permutation(N); for (let x of ans) document.write( x + " "); // This code is contributed by Potta Lokesh </script> |
Output
2 4 1 3 5
Time complexity: O(N)
Auxiliary Space: O(N) because it is using extra space for vector ans.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
