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';
}

Juan Cruz Martinez

¡Hola!

Soy Juan Cruz Martinez, el fundador de LiveCodeStream.dev. Me encanta programar y creo en el poder de la programación no solo para construir un mundo mejor, sino para hacer que TU vida sea mejor.

Fundé LiveCodeStream.dev porque quería ayudarte a aprender a programar, construir una mejor carrera y, en última instancia, crear una vida mejor. Eso me sucedió hace más de una década cuando comencé a programar, y le sucede a decenas de miles de personas a diario. Quiero que TÚ te unas a esa revolución.

No importa cómo lo llames, escribir código, programación, desarrollo de software o cualquier otra cosa, las habilidades involucradas están en una demanda cada vez mayor. Y ya sea que quieras incursionar en el desarrollo de sitios web, diseño de juegos, desarrollo de blockchain o cualquier otra cosa, quiero ayudarte.