hey,

How come hidden test case 4 1 3 2 would return "YES", obvious it should be "NO" right?

Theory: (a, b, c) -> (b, c, a) is a 3-cycle permutation. That means the permutation (b, c, a) of (a, b, c) is achieved by shifting 3 consecutive numbers(cycle) which are sorted.

Now, if a permutation can be built with even number of swaps, then its even permutation, otherwise it is an odd permutation. Our goal is to built the sorted array from the given one by 3-cycle permutation, which is an even permutation itself.

Now, if (i, j) are two indices such that i) i < j ii) A[i] > A[j] then its called an inversion, which simply means this pair on non-consecutive numbers in an array is unsorted.

It is important to note that every swap of two elements change the parity of inversion count. For example, for an array (4, 3, 1) , 4 > 3 ---> inversion count =1 4 > 1 ----> inversion count =2 3 > 1 ----> inversion count = 3 so, inversion count parity is odd if we swap (3, 1) --> (4, 1, 3) now the inversion count will be 2, which is even parity. Just one swap changes the parity odd to even

Now, a 3-cycle permutation is an even permutation, which preserves the parity of inversion count since the permutation is achived by two swaps in a row. That means if we start with an array which have even number of inversion, after doing the 3-cycle permutation on it any given number of times, the array will still have an even number of inversions or vice versa

Our goal is to make the array 0 inversion count, which is actually an even inversion count. Therefore, if the number of inversion in an array is even, then the array can be sorted by 3-cycle permutation, as the initial parity of inversion count(even) will be preserved and ended with inversion count 0(even as well)

solution in c#:

public static string larrysArray(List<int> A)
    {
        int inversionCount =0 ;
        for(int i = 0; i< A.Count; i++)
        {
            for(int j= i; j<A.Count; j++)
            {
                if(A[i] > A[j]) inversionCount++;
            }
        }

    return (inversionCount %2) == 0 ? "YES": "NO";
}

Here is problem solution in python java c++ c and Javascript - https://programmingoneonone.com/hackerrank-larrys-array-problem-solution.html

I use a quite intuitive approach to construct solution in Python. To sort a list using swapping among 3 numbers, one may begin with the smallest number, and moving it forward to the beginning of the list every time by 2 numbers. For example: [5,4,3,2,1] --> [5,4,1,3,2] --> [1,5,4,3,2]. In this case by this iteration alone can bring the smallest number to the front. But in cases like [4,3,2,1], it will become [4,1,3,2], the last swapping moving the first number to third position, ie [1,3,4,2]. By popping out the smallest number(1), we can repeat the procedure to the second smallest(2). At the end there will be two numbers remaining, if first one is smaller than the second, the whole list is sortable, otherwise no.

So the following code is constructed:

def larrysArray(A):
    while len(A) > 2:
        smallest = A.index(min(A))
        while  smallest != 0:
            if smallest >= 2:
                A = A[:smallest - 2] + [A[smallest]] + A[smallest - 2:smallest] + A[smallest + 1:]
            elif smallest == 1:
                A = A[1:3] + [A[0]] + A[3:]
            smallest = A.index(min(A))
        A.pop(0)
    return 'YES' if A[0] < A[1] else 'NO'

The code works but fails about half of the tests due to time limit issue. A review concludes that the repeated reconstructions of the list by moving the smallest number forward 2 positions is unnecessary. At the end either the smallest number, if its index is even, can be moved to position 0 without disturbing other numbers, or it can be moved to position 1 and swap the position 0 number to position 2. The following rewritten code successfully passes all the tests:

def larrysArray(A):
    while len(A) > 2:
        smallest = A.index(min(A))
        if smallest % 2 == 0:
            A = [A[smallest]] + A[:smallest] + A[smallest + 1:]
        else:
            if smallest > 1:
                A = [A[0]] + [A[smallest]] + A[1:smallest] + A[smallest + 1:]
            A = A[1:3] + [A[0]] + A[3:]
        A.pop(0)
    return 'YES' if A[0] < A[1] else 'NO'