Given an integer N and the task is to generate a permutation of the numbers in range [1, N] such that:
- The GCD of all the elements multiplied with their position (not index) is greater than 1
- And if it is not possible return -1.
- If there are multiple possible permutations, print any one of them.
Examples:
Input: N = 8
Output: 2 1 4 3 6 5 8 7
Explanation: The elements multiplied by their positions will 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 greater than 1.Input: N = 9
Output: -1
Explanation: No permutation possible, hence return -1
Approach: The idea to solve the problem is as follows:
Try to make the product of position and the number even, then in that situation GCD will be at least 2.
If there are odd number of elements then it is not possible, because odd elements are one more than possible even positions.
Follow the below steps to solve the problem:
- Store all the even numbers in one vector and all the odd numbers in another vector.
- While generating the permutation:
- Push the even number at even index(i.e odd position because the indexing is 0 based) and
- Odd number at odd index(i.e. even position).
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to generate the permutationvector<int> arrangePermutation(int& N){ vector<int> odd, even, res; // If answer does not exist if (N & 1) { for (int i = 1; i <= N; i++) { res.push_back(-1); } return res; } // Separately store the even numbers // and odd numbers for (int i = 1; i <= N; i++) { if (i & 1) { odd.push_back(i); } else { even.push_back(i); } } int k = 0, j = 0; for (int i = 0; i < N; i++) { // If index is even output the even // number because, (even + 1)*even // = even if (i % 2 == 0) { res.push_back(even[k++]); } else { // If index is odd then output odd // number because (odd+1)*odd = even res.push_back(odd[j++]); } } // Return the result return res;}// Function to print the vectorvoid printResult(vector<int>& res){ for (auto x : res) { cout << x << " "; } cout << endl;}// Driver Codeint main(){ int N = 8; // Function call vector<int> res = arrangePermutation(N); printResult(res); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;import java.util.*;class GFG { // Function to generate the permutation public static int[] arrangePermutation(int N) { ArrayList<Integer> odd = new ArrayList<>(); ArrayList<Integer> even = new ArrayList<>(); int res[] = new int[N]; // If answer does not exist if (N % 2 == 1) { for (int i = 0; i < N; i++) { res[i] = -1; } return res; } // Separately store the even numbers // and odd numbers for (int i = 1; i <= N; i++) { if (i % 2 == 1) { odd.add(i); } else { even.add(i); } } int k = 0, j = 0; for (int i = 0; i < N; i++) { // If index is even output the even // number because, (even + 1)*even // = even if (i % 2 == 0) { res[i] = even.get(k++); } else { // If index is odd then output odd // number because (odd+1)*odd = even res[i] = odd.get(j++); } } // Return the result return res; } // Function to print the array public static void printResult(int res[]) { for (int x : res) { System.out.print(x + " "); } System.out.println(); } // Driver Code public static void main(String[] args) { int N = 8; // Function call int res[] = new int[N]; res = arrangePermutation(N); printResult(res); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the above approach# function to generate the permutationdef arrangePermutation(N): odd = [] even = [] res = [] # if the answer does not exist if N & 1: for i in range(1, N + 1): res.append(-1) return res # separately store the even numbers # and odd numbers for i in range(1, N + 1): if i & 1: odd.append(i) else: even.append(i) k = 0 j = 0 for i in range(N): # if index is even output the even # number because (even + 1) * even = even if i % 2 == 0: res.append(even[k]) k += 1 else: # if index is odd then output odd # number because (odd + 1) * odd = even res.append(odd[j]) j += 1 # return the result return res# function to print the arraydef printResult(res): for x in res: print(x, end=" ") print()# Driver CodeN = 8# function callres = arrangePermutation(N)printResult(res)# This code is contributed by phasing17 |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG { // Function to generate the permutation public static int[] arrangePermutation(int N) { List<int> odd = new List<int>(); List<int> even = new List<int>(); int[] res = new int[N]; // If answer does not exist if (N % 2 == 1) { for (int i = 0; i < N; i++) { res[i] = -1; } return res; } // Separately store the even numbers // and odd numbers for (int i = 1; i <= N; i++) { if (i % 2 == 1) { odd.Add(i); } else { even.Add(i); } } int k = 0, j = 0; for (int i = 0; i < N; i++) { // If index is even output the even // number because, (even + 1)*even // = even if (i % 2 == 0) { res[i] = even[k++]; } else { // If index is odd then output odd // number because (odd+1)*odd = even res[i] = odd[j++]; } } // Return the result return res; } // Function to print the array public static void printResult(int[] res) { foreach (int x in res) { Console.Write(x + " "); } Console.WriteLine(); }// Driver Codepublic static void Main(){ int N = 8; // Function call int[] res = new int[N]; res = arrangePermutation(N); printResult(res);}}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach // Function to generate the permutation function arrangePermutation(N) { let odd = [], even = [], res = []; // If answer does not exist if (N & 1) { for (let i = 1; i <= N; i++) { res.push(-1); } return res; } // Separately store the even numbers // and odd numbers for (let i = 1; i <= N; i++) { if (i & 1) { odd.push(i); } else { even.push(i); } } let k = 0, j = 0; for (let i = 0; i < N; i++) { // If index is even output the even // number because, (even + 1)*even // = even if (i % 2 == 0) { res.push(even[k++]); } else { // If index is odd then output odd // number because (odd+1)*odd = even res.push(odd[j++]); } } // Return the result return res; } // Function to print the vector function printResult(res) { for (let x of res) { document.write(x + " "); } document.write("<br>") } // Driver Code let N = 8; // Function call let res = arrangePermutation(N); printResult(res); // This code is contributed by Potta Lokesh </script> |
Output
2 1 4 3 6 5 8 7
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
