Dado un arr[] de tamaño N cuyos elementos están ordenados en orden descendente. La tarea es encontrar si la array dada se puede clasificar en orden ascendente realizando un número mínimo de intercambios a la derecha cíclicos triples. Imprima los índices involucrados en cada uno de los intercambios de derechos cíclicos triples.
Triple cíclico a la derecha se refiere al triple cíclico a la derecha en el que:
arr[i] -> arr[j] -> arr[k] -> arr[i], donde 0 <= i, j, k < N e i, j y k deben ser diferentes.
Nota: Los siguientes ejemplos tienen indexación basada en 1.
Ejemplos:
Entrada: arr[] = {100, 90, 80, 70, 60}
Salida: SI
2
[1 2 5]
[2 5 4]
Explicación:
Para la primera operación los índices elegidos son 1, 2 y 5 .
arr[1] = arr[5] = 60
arr[2] = arr[1] = 100
arr[5] = arr[2] = 90
La array actualizada después del primer desplazamiento cíclico a la derecha es {60 100 80 70 90}
Para la primera operación los índices elegidos son 2, 5 y 4 .
arr[2] = arr[4] = 70
arr[5] = arr[2] = 100
arr[4] = arr[5] = 90
La array actualizada después del segundo desplazamiento cíclico a la derecha es {60 70 80 90 100}
Así la array está ordenada por solo 2 operaciones cíclicas de intercambio a la derecha.
Entrada: arr[] = {7, 6, 5, 4, 3, 2, 1}
Salida: NO
Explicación:
No es posible realizar ninguna operación cíclica de desplazamiento a la derecha en esta array y, por lo tanto, no se puede clasificar en orden ascendente.
Enfoque:
Se deben hacer las siguientes observaciones:
- Para una array con 3 elementos, la respuesta es NO. Porque el elemento del medio está en su posición correcta y nos quedarán dos elementos, mientras que se necesitan tres elementos para el desplazamiento cíclico a la derecha.
- Si (N % 4) == 0 o (N % 4) == 1 entonces es posible ordenar, de lo contrario no es posible ordenar.
Del enfoque anterior se puede ver que en cada dos desplazamientos cíclicos a la derecha se ordenan cuatro elementos. - Cuando N % 4 == 0 :
Consideremos el arreglo [4 3 2 1]. Después de dos turnos para los índices 1 2 4 y 2 4 3 (en orden), la array se ordena como 1 2 3 4. - Cuando N % 4 == 1 :
Se aplica el ejemplo 1 mencionado anteriormente que usa 5 elementos en la array. El elemento del índice 3 permanece como tal, mientras que los otros 4 elementos se ordenan en 2 desplazamientos cíclicos a la derecha. - Cuando N % 4 == 2 :
no es posible ordenar la array ya que después de ordenar grupos de 4 elementos, finalmente quedarán 2 elementos en un orden incorrecto que nunca se podrá ordenar ya que para ordenar se necesitan exactamente 3 elementos. - Cuando N % 4 == 3 :
No es posible ordenar la array después de grupos de 4 elementos, finalmente 3 elementos quedarán en un orden incorrecto que nunca podrá ordenarse ya que el elemento del medio de estos 3 elementos no ordenados permanece en su lugar. posición correcta desde el principio. Esto nos deja con 2 elementos que nunca se pueden ordenar, ya que para ordenar se necesitan exactamente 3 elementos.
Siga los pasos a continuación para resolver el problema.
- Si el valor de N módulo 4 es 2 o 3, imprima NO .
- Si el valor de N módulo 4 es 0 o 1 entonces,
- Imprimir SÍ
- Imprima el valor de piso (N / 2), ya que piso (N / 2) es el número de operaciones cíclicas de intercambio a la derecha que se van a realizar.
- Inicializar una variable K a 1.
- Las operaciones cíclicas de swap a la derecha solo se pueden realizar en pares. Los pares son [K, K+1, N] y [K+1, N, N-1]. Tan pronto como se impriman los pares, incremente el valor de K en 2 y disminuya el valor de N en 2.
- Continúe realizando el paso 4 hasta que se impriman todas las operaciones de piso (N/2) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
void sortarray(int arr[],int N)
{
// If array is 3 2 1 can't
// be sorted because 2 is in
// its correct position, 1
// and 3 can't shift right
// because cyclic right shift
// takes place between 3 elements
if(N == 3)
cout << "NO" << endl;
// Check if its possible to sort
else if(N % 4 == 0 || N % 4 == 1)
{
cout << "YES" << endl;
// Number of swap is
// N / 2 always
// for this approach
cout << (N / 2) << endl;
int k = 1;
// Printing index of the
// cyclic right shift
for(int l = 0; l < (N / 4); l++)
{
cout << k << " " << k + 1
<< " " << N << endl;
cout << k + 1 << " " << N
<< " " << N - 1 << endl;
k = k + 2;
N = N - 2;
}
}
else
cout << "NO" << endl;
}
// Driver code
int main()
{
int N = 5;
int arr[] = { 5, 4, 3, 2, 1 };
sortarray(arr, N);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program for the above approach
class GFG{
static void sortarray(int arr[], int N)
{
// If array is 3 2 1 can't
// be sorted because 2 is in
// its correct position, 1
// and 3 can't shift right
// because cyclic right shift
// takes place between 3 elements
if(N == 3)
System.out.println("NO");
// Check if its possible to sort
else if(N % 4 == 0 || N % 4 == 1)
{
System.out.println("YES");
// Number of swap is
// N / 2 always
// for this approach
System.out.println(N / 2);
int k = 1, l;
// Printing index of the
// cyclic right shift
for(l = 0; l < (N / 4); l++)
{
System.out.println(k + " " + (k + 1) +
" " + N);
System.out.println(k + 1 + " " +
N + " " + (N - 1));
k = k + 2;
N = N - 2;
}
}
else
System.out.println("NO");
}
// Driver code
public static void main (String []args)
{
int N = 5;
int arr[] = { 5, 4, 3, 2, 1 };
sortarray(arr, N);
}
}
// This code is contributed by chitranayal
Python3
# Python3 program for the above approach
def sortarray(arr, N):
# if array is 3 2 1 can't
# be sorted because 2 is in
# its correct position, 1
# and 3 can't shift right
# because cyclic right shift
# takes place between 3 elements
if(N == 3):
print("NO")
# check if its possible to sort
elif(N % 4 == 0
or N % 4 == 1):
print("YES")
# Number of swap is
# N / 2 always
# for this approach
print(N // 2)
k = 1
# printing index of the
# cyclic right shift
for l in range(N // 4):
print(k, k + 1, N)
print(k + 1, N, N-1)
k = k + 2
N = N - 2
else:
print("NO")
# Driver code
if __name__ == "__main__":
N = 5
arr = [5, 4, 3, 2, 1]
sortarray(arr, N)
C#
// C# program for the above approach
using System;
class GFG{
static void sortarray(int[] arr, int N)
{
// If array is 3 2 1 can't
// be sorted because 2 is in
// its correct position, 1
// and 3 can't shift right
// because cyclic right shift
// takes place between 3 elements
if(N == 3)
Console.WriteLine("NO");
// Check if its possible to sort
else if(N % 4 == 0 || N % 4 == 1)
{
Console.WriteLine("YES");
// Number of swap is
// N / 2 always
// for this approach
Console.WriteLine(N / 2);
int k = 1;
// Printing index of the
// cyclic right shift
for(int l = 0; l < (N / 4); l++)
{
Console.WriteLine(k + " " + (k + 1) +
" " + N);
Console.WriteLine(k + 1 + " " + N +
" " + (N - 1));
k = k + 2;
N = N - 2;
}
}
else
Console.WriteLine("NO");
}
// Driver code
public static void Main()
{
int N = 5;
int []arr = { 5, 4, 3, 2, 1 };
sortarray(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
function sortarray(arr,N)
{
// If array is 3 2 1 can't
// be sorted because 2 is in
// its correct position, 1
// and 3 can't shift right
// because cyclic right shift
// takes place between 3 elements
if(N == 3)
document.write("NO<br>");
// Check if its possible to sort
else if(N % 4 == 0 || N % 4 == 1)
{
document.write("YES<br>");
// Number of swap is
// N / 2 always
// for this approach
document.write(Math.floor(N / 2)+"<br>");
let k = 1, l;
// Printing index of the
// cyclic right shift
for(l = 0; l < Math.floor(N / 4); l++)
{
document.write(k + " " + (k + 1) +
" " + N+"<br>");
document.write(k + 1 + " " +
N + " " + (N - 1)+"<br>");
k = k + 2;
N = N - 2;
}
}
else
document.write("NO<br>");
}
// Driver code
let N = 5;
let arr=[ 5, 4, 3, 2, 1];
sortarray(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
YES 2 1 2 5 2 5 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)