Given a number N, the task is to find a permutation A[] of first N integers such that the absolute difference of adjacent elements is at least 2 i.e., | Ai+1 ? Ai | ? 2 for all 0 ? i < N?1.If no such permutation exists, print -1.
Examples:
Input: N = 4
Output: 3 1 4 2
?Explanation: Here A[] = {3, 1, 4, 2} satisfies the given condition.
Since | Ai+1 ? Ai | ? 2 for all 0 ? i < N?1Input: N = 2
Output: -1
Explanation: No such permutation is possible that satisfies the given condition
Approach: The problem can be solved based on the following observation:
- If N = 2 or N = 3, then no array exists that satisfy the above condition.
- Otherwise, array exists that satisfy the above condition such as:
- First print all odd numbers from N to 1 in decreasing order and after that print all even numbers in decreasing order.
Follow the steps mentioned below to implement the idea:
- If N = 2 or N = 3, print -1.
- Otherwise, check whether N is odd or even:
- If N is odd, iterate a loop from N to 1 to print all odd numbers after that iterate another loop from N – 1 to 2 to print even numbers.
- If N is even, iterate a loop from N – 1 to 1 to print all odd numbers after that iterate another loop from N to 2 to print even numbers.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the arrayvoid findArray(int n){ if (n == 2 || n == 3) cout << -1; else { // If n is odd if ((n % 2) == 1) { // Loops to print the permutation for (int i = n; i >= 1; i -= 2) { cout << i << " "; } for (int i = n - 1; i >= 2; i -= 2) { cout << i << " "; } } // If n is even else { // Loops to print the permutation for (int i = n - 1; i >= 1; i -= 2) { cout << i << " "; } for (int i = n; i >= 2; i -= 2) { cout << i << " "; } } }}// Driver Codeint main(){ int N = 4; // Function call findArray(N); return 0;}// This code is contributed by aarohirai2616. |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;public class GFG { // Function to find the array public static void findArray(int n) { if (n == 2 || n == 3) System.out.println(-1); else { // If n is odd if ((n % 2) == 1) { // Loops to print the permutation for (int i = n; i >= 1; i -= 2) { System.out.print(i + " "); } for (int i = n - 1; i >= 2; i -= 2) { System.out.print(i + " "); } } // If n is even else { // Loop to print the permutation for (int i = n - 1; i >= 1; i -= 2) { System.out.print(i + " "); } for (int i = n; i >= 2; i -= 2) { System.out.print(i + " "); } } System.out.println(); } } // Driver code public static void main(String[] args) { int N = 4; // Function call findArray(N); }} |
Python3
# Python3 code to implement the approach# Function to find the arraydef findArray(n): if (n == 2 or n == 3) : print(-1); else : # If n is odd if ((n % 2) == 1) : # Loops to print the permutation for i in range(n, 0, -2) : print(i,end=" "); for i in range(n - 1, 1, -2) : print(i,end = " "); # If n is even else : # Loops to print the permutation for i in range( n - 1, 0, -2) : print(i,end=" "); for i in range(n, 1, -2) : print(i, end=" ");# Driver Codeif __name__ == "__main__" : N = 4; # Function call findArray(N); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;public class GFG { // Function to find the array static void findArray(int n) { if (n == 2 || n == 3) Console.WriteLine(-1); else { // If n is odd if ((n % 2) == 1) { // Loops to print the permutation for (int i = n; i >= 1; i -= 2) { Console.Write(i + " "); } for (int i = n - 1; i >= 2; i -= 2) { Console.Write(i + " "); } } // If n is even else { // Loop to print the permutation for (int i = n - 1; i >= 1; i -= 2) { Console.Write(i + " "); } for (int i = n; i >= 2; i -= 2) { Console.Write(i + " "); } } Console.WriteLine(); } } static public void Main() { // Code int N = 4; // Function call findArray(N); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approach // Function to find the array function findArray(n) { if (n == 2 || n == 3) process.stdout.write(-1); else { // If n is odd if ((n % 2) == 1) { // Loops to print the permutation for (let i = n; i >= 1; i -= 2) { process.stdout.write(i + " "); } for (let i = n - 1; i >= 2; i -= 2) { process.stdout.write(i + " "); } } // If n is even else { // Loop to print the permutation for (let i = n - 1; i >= 1; i -= 2) { process.stdout.write(i + " "); } for (let i = n; i >= 2; i -= 2) { process.stdout.write(i + " "); } } } } // Driver code let N = 4; // Function call findArray(N); // This code is contributed by aarohirai2616. |
Output
3 1 4 2
Time Complexity: O(N)
Auxiliary Space: O(1)
Share your thoughts in the comments