CareerCup

Here are two observations about the problem:
- For arrays with an odd number of elements, the element in the middle cannot be moved.
- Any element can only be moved to its "mirror" index when you pivot around the center, so the element at index 0, can only move to the index "length - 1"

The "simple" brute force approach would be to try every possible rotation and see if one is found.
Given the second observation above, by rotating around the center each element in the array can have one of two possible values - the value at index i or the value at index "length - 1 - i". For an array with n elements, that means there are 2^n combinations. So Running time would be O(2^n) and memory usage would be O(1).

An alternative approach would be to make a copy of the array, sort that copy and compare each element of the sorted copy to the equivalent element of the original array and it's mirror image when pivot around the center.

Sorting takes O(n lg n) and we make up to 2n comparisons, so the runtime is O(n lg n).
We need a "helper" array with n elements, so the memory needed is O(n).

In Java, the code would look like this:

public String canBeSortedByReverse(int[] A) {
		int[] B = Arrays.copyOf(A, A.length);
		Arrays.sort(B);
		for (int i = 0; i < A.length; i++) {
			if (!(A[i] == B[i]) && ! (A[A.length - 1 - i] == B[i])) {
				return "Not Possible";
			}
		}
		return "Possible";
	}

public boolean canSortByReversing(int[] input) {

if(input.length % 2 == 0)
	return false;
int middle = input[input.length / 2];
int i = 0,j = input.length - 1,max=0,min=10000;
for(;i != j;i++,j--) {
	
	int left = input[i];
	int right = input[j];
	if(!orderable(left,middle,right))
		return false;
	boolean reverseRequired = right < left;
	
	int newMax = left,newMin = right;
	if(reverseRequired) {
	   newMax = right;
	   newMin = left;
	}
	if(newMax >= max && newMin <= minRight) {
		max = newMax;
		min = newMin;
		continue;
	}
	
	return false;
}

return true;
}

public boolean orderable(int left,int middle,int right) {
	return ((left <= middle) && (middle <= right)) || ((left >= middle) && (middle >= right));
}

public boolean canSortByReversing(int[] input) {

if(input.length % 2 == 0)
return false;
int middle = input[input.length / 2];
int i = 0,j = input.length - 1,max=0,min=10000;
for(;i != j;i++,j--) {

int left = input[i];
int right = input[j];
if(!orderable(left,middle,right))
return false;
boolean reverseRequired = right < left;

int newMax = left,newMin = right;
if(reverseRequired) {
newMax = right;
newMin = left;
}
if(newMax >= max && newMin <= minRight) {
max = newMax;
min = newMin;
continue;
}

return false;
}

return true;
}

public boolean orderable(int left,int middle,int right) {
return ((left <= middle) && (middle <= right)) || ((left >= middle) && (middle >= right));
}

Swift 2.2

func isSwapSortPossible(array: [Int]) -> String {
    if (array.count <= 1) {
        return "Possble!"
        
    } else if (array.count % 2 == 0) {
        return "Not Possible"
        
    }
    
    let sortedArray = array.sort({ return $0 < $1 })
    let mid = array.count / 2
    
    for i in 1 ..< mid {
        let left = array[mid - i]
        let right = array[mid + i]
        let sortedLeft = sortedArray[mid - i]
        let sortedRight = sortedArray[mid + i]
        // If left and right don't pair up and match
        if ((left != sortedLeft || right != sortedRight) &&
            (left != sortedRight || right != sortedLeft)) {
            return "Not Possible!"
            
        }
        
    }
    return "Possible!"
    
}

isSwapSortPossible([1, 6, 3, 4, 5, 2, 7]) // "Possible!"
isSwapSortPossible([2, 6, 5, 1, 7, 5, 4]) // "Not Possible!"

What about O(N) solution with a simple walkthrough of a copy of the array and swapping elements with mirror index values whenever they don't follow a normal sort order.

We can do that as all the sub-elements between the swapped ones can be put in the same order with another reverse operation.

If a is a copy of the original array, then in C++:

bool possible(int *a, const int n) {

	int i, t;

	for (i=0; i<n/2; ++i) {
		if (a[i] > a[n-1-i]) {
			t = a[i];
			a[i] = a[n-1-i];
			a[n-1-i] = t;
		}
	}

	for (i=0; i<n-1; ++i) {
		if (a[i] > a[i+1]) {
			return false;
		}
	}

	return true;
}

/*
1) all elements on the left must be <= than the element in the 
   middle after n such mirror operations.
2) Most perumtations that are possible are 2^(n/2), that is, 
   swap index 0 with n-1, index 1 with n-2, etc... 
   (independently if given mirror operation is performed outwards inwards)
3) Every element, except the middle one has two possible values, 
   it's value at index or it's value at mirrored index

Solution: 
  f[i] = min(a[i], a[n-1-i]) for 0<=i<n/2
  e[i] = max(a[i], a[n-1-i]) for 0<=i<n/2

  Iterate through the array 1 to n/2-1 and check if:
    f[i]>=f[i-1] AND e[i]>=e[i-1]

  If that succeeded and length of a is odd, only need to check 
  f[n/2-1] <= a[n/2] <= e[n/2+1] if that's true, its sortable, 
  obviously if array length is even, if above iteration succeeded with all checks
  it is sortable.

  Time complexity O(N)
  Space complexicty O(1)
*/

#include <iostream>
#include <algorithm>

using namespace std;

// array with n-elements
bool IsSortable(const int a[], int n)
{
	for (int i = 1; i < n/2; ++i)
	{
		if (min(a[i], a[n - i - 1]) < min(a[i - 1], a[n - i])) 
			return false;
		if (max(a[i], a[n - i - 1]) > max(a[i - 1], a[n - i])) 
			return false;
	}
	if (n & 1 == 1)
		return min(a[n / 2 - 1], a[n / 2 + 1]) <= a[n / 2] &&
			   max(a[n / 2 - 1], a[n / 2 + 1]) >= a[n / 2];
	return true;
}



int main()
{
	int a1[]{ 1,2,3,4,5 };
	cout << "a1: " << IsSortable(a1, sizeof(a1)/sizeof(int)) << endl;
	
	int a2[]{ 5,4,3,2,1 };
	cout << "a2: " << IsSortable(a2, sizeof(a2) / sizeof(int)) << endl;

	int a3[]{ 1,2,6,3,4 };
	cout << "a3: " << IsSortable(a3, sizeof(a3) / sizeof(int)) << endl;

	int a4[]{ 4,2,1,2 };
	cout << "a4: " << IsSortable(a4, sizeof(a4) / sizeof(int)) << endl;

	int a5[]{ 9,8,7,6,5,4,3,2,1 };
	cout << "a5: " << IsSortable(a5, sizeof(a5) / sizeof(int)) << endl;

	int a6[]{ 9,8,7,6,5,4,5,2,1 };
	cout << "a6: " << IsSortable(a6, sizeof(a6) / sizeof(int)) << endl;
}

static void IsSortableByReversing()
        {
            int[] input = { 1, 6, 8, 4, 5, 2, 7 };
            int mid = input.Length / 2;
            int increment = 1;

            while (mid - increment >= 0)
            {
                if((input[mid + increment] > input[mid] && input[mid - increment] > input[mid]) || 
                    (input[mid + increment] < input[mid] && input[mid - increment] < input[mid]))
                {
                    Console.WriteLine("Not Possible");
                    Console.ReadLine();
                }

                increment++;
            }
            Console.WriteLine("Possible");
            Console.ReadLine();
        }