Dado un número entero N y la tarea es generar una permutación de los números en el rango [ 1, N ] tal que:
- El MCD de todos los elementos multiplicado por su posición (no índice) es mayor que 1
- Y si no es posible devuelve -1.
- Si hay varias permutaciones posibles, imprima cualquiera de ellas.
Ejemplos:
Entrada: N = 8
Salida: 2 1 4 3 6 5 8 7
Explicación: Los elementos multiplicados por sus posiciones serán
{2*1, 1*2, 4*3, 3*4, 6*5, 5*6, 8*7, 7*8} = {2, 2, 12, 12, 30, 30, 56, 56}.
El MCD de todos estos números = 2 que es mayor que 1.Entrada: N = 9
Salida: -1
Explicación: No es posible la permutación, por lo tanto, devuelve -1
Planteamiento: La idea para resolver el problema es la siguiente:
Intenta hacer que el producto de la posición y el número sea par, entonces en esa situación GCD será al menos 2.
Si hay un número impar de elementos entonces no es posible, porque los elementos impares son uno más que las posibles posiciones pares.
Siga los pasos a continuación para resolver el problema:
- Almacene todos los números pares en un vector y todos los números impares en otro vector.
- Al generar la permutación:
- Presione el número par en el índice par (es decir, en la posición impar porque la indexación se basa en 0) y
- Número impar en índice impar (es decir, posición par).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate the permutation
vector<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 vector
void printResult(vector<int>& res)
{
for (auto x : res) {
cout << x << " ";
}
cout << endl;
}
// Driver Code
int main()
{
int N = 8;
// Function call
vector<int> res = arrangePermutation(N);
printResult(res);
return 0;
}
Java
// Java code to implement the above approach
import 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 permutation def 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 array def printResult(res): for x in res: print(x, end=" ") print() # Driver Code N = 8 # function call res = arrangePermutation(N) printResult(res) # This code is contributed by phasing17
C#
// C# code for the above approach
using 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 Code
public 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>
Producción
2 1 4 3 6 5 8 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)