Dado un número entero N . La tarea es encontrar la permutación de los primeros N números naturales tal que la diferencia absoluta entre dos números consecutivos cualesquiera > 1 . Si no es posible tal permutación, imprima -1 .
Ejemplos:
Entrada: N = 5
Salida: 5 3 1 4 2Entrada: N = 3
Salida: -1
Enfoque: puede haber muchos arreglos posibles, pero uno de los enfoques más comunes y codiciosos es ordenar todos los números impares en orden decreciente (o creciente) y luego ordenar todos los números pares en orden decreciente (o creciente). Tenga en cuenta que si N = 3 o N = 2 , entonces no habrá tal arreglo posible y si N = 1 , entonces la secuencia consistirá en un solo elemento, es decir, 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the required permutation
void arrange(int N)
{
if (N == 1) {
cout << "1";
return;
}
// No permutation is possible
// satisfying the given condition
if (N == 2 || N == 3) {
cout << "-1";
return;
}
// Maximum even and odd elements < N
int even = -1, odd = -1;
if (N % 2 == 0) {
even = N;
odd = N - 1;
}
else {
odd = N;
even = N - 1;
}
// Print all odd elements in decreasing order
while (odd >= 1) {
cout << odd << " ";
// Next element must be odd
odd = odd - 2;
}
// Print all even elements in decreasing order
while (even >= 2) {
cout << even << " ";
// Next element must be even
even = even - 2;
}
}
// Driver code
int main()
{
int N = 5;
arrange(N);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to print the required
// permutation
static void arrange(int N)
{
if (N == 1)
{
System.out.println("1");
return;
}
// No permutation is possible
// satisfying the given condition
if (N == 2 || N == 3)
{
System.out.println("-1");
return;
}
// Maximum even and odd elements < N
int even = -1, odd = -1;
if (N % 2 == 0)
{
even = N;
odd = N - 1;
}
else
{
odd = N;
even = N - 1;
}
// Print all odd elements in
// decreasing order
while (odd >= 1)
{
System.out.print(odd);
System.out.print(" ");
// Next element must be odd
odd = odd - 2;
}
// Print all even elements in
// decreasing order
while (even >= 2)
{
System.out.print(even);
System.out.print(" ");
// Next element must be even
even = even - 2;
}
}
// Driver code
public static void main(String[] args)
{
int N = 5;
arrange(N);
}
}
// This code is contributed
// by Akanksha Rai
Python3
# Python3 implementation of the approach
# Function to print the required permutation
def arrange(N):
if (N == 1) :
print("1")
return
# No permutation is possible
# satisfying the given condition
if (N == 2 or N == 3) :
print("-1")
return
# Maximum even and odd elements < N
even = -1
odd = -1
if (N % 2 == 0):
even = N
odd = N - 1
else :
odd = N
even = N - 1
# Print all odd elements in
# decreasing order
while (odd >= 1):
print(odd, end = " ")
# Next element must be odd
odd = odd - 2
# Print all even elements in
# decreasing order
while (even >= 2):
print(even, end = " ")
# Next element must be even
even = even - 2
# Driver code
if __name__ == "__main__":
N = 5
arrange(N)
# This code is contributed by ita_c
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print the required
// permutation
static void arrange(int N)
{
if (N == 1)
{
Console.WriteLine("1");
return;
}
// No permutation is possible
// satisfying the given condition
if (N == 2 || N == 3)
{
Console.WriteLine("-1");
return;
}
// Maximum even and odd elements < N
int even = -1, odd = -1;
if (N % 2 == 0)
{
even = N;
odd = N - 1;
}
else
{
odd = N;
even = N - 1;
}
// Print all odd elements in
// decreasing order
while (odd >= 1)
{
Console.Write(odd);
Console.Write(" ");
// Next element must be odd
odd = odd - 2;
}
// Print all even elements in
// decreasing order
while (even >= 2)
{
Console.Write(even);
Console.Write(" ");
// Next element must be even
even = even - 2;
}
}
// Driver code
public static void Main()
{
int N = 5;
arrange(N);
}
}
// This code is contributed
// by Shivi_Aggarwal
PHP
<?php
// PHP implementation of the approach
// Function to print the required
// permutation
function arrange($N)
{
if ($N == 1)
{
echo "1";
return;
}
// No permutation is possible
// satisfying the given condition
if ($N == 2 || $N == 3)
{
echo "-1";
return;
}
// Maximum even and odd elements < N
$even = -1 ;
$odd = -1;
if ($N % 2 == 0)
{
$even = $N;
$odd = $N - 1;
}
else
{
$odd = $N;
$even = $N - 1;
}
// Print all odd elements in
// decreasing order
while ($odd >= 1)
{
echo $odd, " ";
// Next element must be odd
$odd = $odd - 2;
}
// Print all even elements in
// decreasing order
while ($even >= 2)
{
echo $even, " ";
// Next element must be even
$even = $even - 2;
}
}
// Driver code
$N = 5;
arrange($N);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to print var the required
// permutation
function arrange(N)
{
if (N == 1)
{
document.write("1");
return;
}
// No permutation is possible
// satisfying the given condition
if (N == 2 || N == 3)
{
document.write("-1");
return;
}
// Maximum even and odd elements < N
var even = -1, odd = -1;
if (N % 2 == 0)
{
even = N;
odd = N - 1;
}
else
{
odd = N;
even = N - 1;
}
// Print var all odd elements in
// decreasing order
while (odd >= 1)
{
document.write(odd);
document.write(" ");
// Next element must be odd
odd = odd - 2;
}
// Print var all even elements in
// decreasing order
while (even >= 2)
{
document.write(even);
document.write(" ");
// Next element must be even
even = even - 2;
}
}
// Driver code
var N = 5;
arrange(N);
// This code is contributed by umadevi9616
</script>
Producción:
5 3 1 4 2