Sorting array with reverse around middle

Consider the given array arr[], we need to find if we can sort array with the given operation. The operation is 

1. We have to select a subarray from the given array such that the middle element(or elements (in case of even 
   number of elements)) of subarray is also the middle element(or elements (in case of even number of elements)) of 
   the given array. 
2. Then we have to reverse the selected subarray and place this reversed subarray in the array. 
   We can do the above operation as many times as we want. The task is to find if we can sort array with the given operation. 

Examples:  

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

One solution is we can rotate each element around the center, which gives two possibilities in the array i.e. the value at index 'i' or the value at index "length - 1 - i". 
If array has n elements then 2^n combinations possible thus running time would be O(2^n).

Another solution can be make copy of the array and sort the copied array. Then compare each element of the sorted array with equivalent element of original array and its mirror image when pivot around center. Sorting the array takes O(n*logn) and 2n comparisons be required thus running time would be O(n*logn).

Implementation:

// 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 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 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# 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 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 ?> 

<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

Time Complexity: O(n log n), where n is the size of the input array. This is because of the sorting operation performed on the copied array.

Auxiliary Space: O(n), where n is the size of the input array. This is because of the copy of the original array created.