Considere la array dada arr[], necesitamos encontrar si podemos ordenar la array con la operación dada. La operación es
1. Tenemos que seleccionar un subarreglo del arreglo dado tal que el elemento medio (o elementos (en el caso de un
número par de elementos)) del subarreglo sea también el elemento medio (o elementos (en el caso de un número par de elementos) elementos)) de
la array dada.
2. Luego tenemos que invertir el subarreglo seleccionado y colocar este subarreglo invertido en el arreglo.
Podemos hacer la operación anterior tantas veces como queramos. La tarea es encontrar si podemos ordenar la array con la operación dada.
Ejemplos:
Input : arr[] = {1, 6, 3, 4, 5, 2, 7}
Output : Yes
We can choose sub-array[3, 4, 5] on
reversing this we get [1, 6, 5, 4, 3, 2, 7]
again on selecting [6, 5, 4, 3, 2] and
reversing this one we get [1, 2, 3, 4, 5, 6, 7]
which is sorted at last thus it is possible
to sort on multiple reverse operation.
Input : arr[] = {1, 6, 3, 4, 5, 7, 2}
Output : No
Una solución es que podemos rotar cada elemento alrededor del centro, lo que da dos posibilidades en la array, es decir, el valor en el índice ‘i’ o el valor en el índice «longitud – 1 – i».
Si la array tiene n elementos, entonces 2 ^ n combinaciones posibles, por lo que el tiempo de ejecución sería O (2 ^ n).
Otra solución puede ser hacer una copia de la array y ordenar la array copiada. Luego compare cada elemento de la array ordenada con el elemento equivalente de la array original y su imagen especular cuando gire alrededor del centro. Ordenar la array requiere O (n * logn) y se requieren 2n comparaciones, por lo que el tiempo de ejecución sería O (n * logn).
C++
// CPP program to find possibility to sort
// by multiple subarray reverse operation
#include <bits/stdc++.h>
using namespace std;
bool ifPossible(int arr[], int n)
{
int cp[n];
// making the copy of the original array
copy(arr, arr + n, cp);
// sorting the copied array
sort(cp, cp + n);
for (int i = 0; i < n; i++) {
// checking mirror image of elements of sorted
// copy array and equivalent element of original
// array
if (!(arr[i] == cp[i]) && !(arr[n - 1 - i] == cp[i]))
return false;
}
return true;
}
// driver code
int main()
{
int arr[] = { 1, 7, 6, 4, 5, 3, 2, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
if (ifPossible(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to find possibility to sort
// by multiple subarray reverse operation
import java.util.*;
class GFG {
static boolean ifPossible(int arr[], int n)
{
// making the copy of the original array
int copy[] = Arrays.copyOf(arr, arr.length);
// sorting the copied array
Arrays.sort(copy);
for (int i = 0; i < n; i++) {
// checking mirror image of elements of
// sorted copy array and equivalent element
// of original array
if (!(arr[i] == copy[i]) && !(arr[n - 1 - i] == copy[i]))
return false;
}
return true;
}
// driver code
public static void main(String[] args)
{
int arr[] = { 1, 7, 6, 4, 5, 3, 2, 8 };
int n = arr.length;
if (ifPossible(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
Python 3
# Python 3 program to find
# possibility to sort by
# multiple subarray reverse
# operation
def ifPossible(arr, n):
cp = [0] * n
# making the copy of
# the original array
cp = arr
# sorting the copied array
cp.sort()
for i in range(0 , n) :
# checking mirror image of
# elements of sorted copy
# array and equivalent element
# of original array
if (not(arr[i] == cp[i]) and not
(arr[n - 1 - i] == cp[i])):
return False
return True
# Driver code
arr = [1, 7, 6, 4, 5, 3, 2, 8]
n = len(arr)
if (ifPossible(arr, n)):
print("Yes")
else:
print("No")
# This code is contributed by Smitha
C#
// C# Program to answer queries on sum
// of sum of odd number digits of all
// the factors of a number
using System;
class GFG {
static bool ifPossible(int []arr, int n)
{
int []cp = new int[n];
// making the copy of the original
// array
Array.Copy(arr, cp, n);
// sorting the copied array
Array.Sort(cp);
for (int i = 0; i < n; i++) {
// checking mirror image of
// elements of sorted copy
// array and equivalent element
// of original array
if (!(arr[i] == cp[i]) &&
!(arr[n - 1 - i] == cp[i]))
return false;
}
return true;
}
// Driver code
public static void Main()
{
int []arr = new int[]{ 1, 7, 6, 4,
5, 3, 2, 8 };
int n = arr.Length;
if (ifPossible(arr, n))
Console.WriteLine( "Yes");
else
Console.WriteLine( "No");
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find possibility to sort
// by multiple subarray reverse operation
function ifPossible(&$arr, $n)
{
$cp = array();
// making the copy of the
// original array
$cp = $arr;
// sorting the copied array
sort($cp);
for ($i = 0; $i < $n; $i++)
{
// checking mirror image of elements
// of sorted copy array and equivalent
// element of original array
if (!($arr[$i] == $cp[$i]) &&
!($arr[$n - 1 - $i] == $cp[$i]))
return false;
}
return true;
}
// Driver code
$arr = array(1, 7, 6, 4, 5, 3, 2, 8);
$n = sizeof($arr);
if (ifPossible($arr, $n))
echo "Yes";
else
echo "No";
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to find possibility to sort
// by multiple subarray reverse operation
function ifPossible(arr, n)
{
// making the copy of the original array
let copy = arr;
// sorting the copied array
copy.sort();
for (let i = 0; i < n; i++) {
// checking mirror image of elements of
// sorted copy array and equivalent element
// of original array
if (!(arr[i] == copy[i]) && !(arr[n - 1 - i] == copy[i]))
return false;
}
return true;
}
// driver code
let arr = [ 1, 7, 6, 4, 5, 3, 2, 8 ];
let n = arr.length;
if (ifPossible(arr, n))
document.write("Yes");
else
document.write("No");;
</script>
Yes