# Larry's Array

## Problem

Larry has been given a permutation of a sequence of natural numbers incrementing from `1`

as an array. He must determine whether the array can be sorted using the following operation any number of times:

- Choose any consecutive indices and rotate their elements in such a way that
`ABC -> BCA -> CAB -> ABC`

.

For example, if :

```
A rotate
[1,6,5,2,4,3] [6,5,2]
[1,5,2,6,4,3] [5,2,6]
[1,2,6,5,4,3] [5,4,3]
[1,2,6,3,5,4] [6,3,5]
[1,2,3,5,6,4] [5,6,4]
[1,2,3,4,5,6]
YES
```

On a new line for each test case, print `YES`

if `A`

can be fully sorted. Otherwise, print `NO`

.

Read more on the challenge page…

## My Solution

I’m providing the solution for Python and JS, please leave on the comments if you found a better way.

That I could think of, there are 2 approaches to solve this problem. The first one being the obvious, doing all the permutations and evaluating at the end when 2 items are left if they are in order.

The other way, which happens I knew it already, has to do with inversion . Inversions are particularly interesting for this problem. Now if you don’t know about inversions, is very unlikely to find this solution on your own.

By definition, The **inversion number** is the cardinality of inversion set. It is a common measure of the sortedness of a permutation or sequence.

What’s an interesting property of the inversion number is that the order of the permutation won’t actually affect its even/odd nature for the entire array.

Here is that demonstrated with a few examples:

```
Example 1: 312
inversion(312) = 2
312 -> 123 = sorted!
Example 2: 231
inversion(231) = 2
231 -> 312 -> 123 = sorted!
Example 3: 213
inversion(231) = 1
213 -> 132 -> 321 -> 213 != can't be sorted
```

So we can say that only those combinations with even inversion number can be sorted, and that’s what we are going for.

```
def larrysArray(A):
inversion = 0
for i in range(len(A)):
for j in range(i+1, len(A)):
if (A[i] > A[j]):
inversion += 1
if inversion % 2 == 0:
return 'YES'
else:
return 'NO'
```

```
function larrysArray(A) {
let inversion = 0;
for (let i=0;i<A.length;i++)
for (let j=i+1;j<A.length;j++)
if (A[i] > A[j])
inversion++;
if (inversion % 2 == 0)
return 'YES';
return 'NO';
}
```

## Join the Free Newsletter

A free, weekly e-mail with the best new articles, courses, and special bonuses.

We won't send you spam. Unsubscribe at any time.