HackerRank Larry's Array Problem Solution

In this post, we will solve HackerRank Larry’s Array Problem Solution.

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 3 consecutive indices and rotate their elements in such a way that ABC BCA → CAB → ABC.
For example, if A = {1, 6, 5, 2, 4, 3}:

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.

Function Description

Complete the larrysArray function in the editor below. It must return a string, either YES or NO.

larrysArray has the following parameter(s):

A: an array of integers

Input Format
The first line contains an integer t, the number of test cases.
The next t pairs of lines are as follows:

The first line contains an integer n, the length of A.
The next line contains n space-separated integers A[i].

Output Format
For each test case, print YES if A can be fully sorted. Otherwise, print NO.

Sample Input

Sample Output

YES
YES
NO

Explanation
In the explanation below, the subscript of A denotes the number of operations performed.
Test Case 0:
Ao = {3, 1, 2}→ rotate(3, 1, 2)→ A₁ = {1,2,3}
A is now sorted, so we print Yes on a new line.
Test Case 1:
Ao = {1,3,4,2}→ rotate(3, 4, 2)→ A₁ = {1, 4, 2, 3}. A₁ = {1, 4, 2, 3} → rotate(4, 2, 3) → A₂ = {1, 2, 3, 4}.
A is now sorted, so we print Yes on a new line.
Test Case 2:
No sequence of rotations will result in a sorted A. Thus, we print No on a new line.

HackerRank Larry's Array Problem Solution — HackerRank Larry’s Array Problem Solution

Larry’s Array C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int testcases;
    scanf("%d", &testcases);
    //printf ("%d", testcases);
    int cases = 0;
    while (cases < testcases) {
        int len;
        scanf("%d", &len);
        int value[len-1];
        int i = 0;
        while (i < len){
            scanf("%d", &value[i]);
            i++;
        }
        i = 0;
        int temp = 0;
        while (i < len) {
            int j = i+1;
            while (j < len) {
                if (value[i] > value[j]) {
                    temp++;
                }
                j++;
            }
            i++;
        }
        if (temp%2 == 0) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
        cases++;
    }
    return 0;
}

Larry’s Array C++ Solution

#include <stdio.h>
#include <assert.h>

typedef unsigned int uint_t;
const uint_t T = 10, N = 1000;

static uint_t calc_invs(const uint_t *as, uint_t n) {
    uint_t res = 0;
    for (uint_t i = 1; i < n; i++) {
        for (uint_t j = 0; j < i; j++)
            res += (as[j] > as[i]);
    }
    return res;
}

static uint_t as[N];

int main() {
    uint_t t;
    int st = scanf("%u", &t);
    assert (st == 1);
    assert (0 < t && t <= T);
    for (uint_t i = 0; i < t; i++) {
        uint_t n;
        st = scanf("%u", &n);
        assert (3 <= n && n <= N);
        for (uint_t j = 0; j < n; j++) {
            st = scanf("%u", &as[j]);
            assert (st == 1);
            assert (0 < as[j] && as[j] <= n);
        }
        uint_t res = calc_invs(as, n) & 1;
        printf("%s\n", res ? "NO" : "YES");
    }
    
    return 0;
}

Larry’s Array C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static void Main(String[] args) {
        int t = Convert.ToInt32(Console.ReadLine());
            for(int i=0; i<t; i++)
            {
                int n = Convert.ToInt32(Console.ReadLine());
                string[] temp = Console.ReadLine().Split(' ');
                int[] arr = Array.ConvertAll(temp,Int32.Parse);
                int[] cnt = new int[n];
                try
                {
                    for(int j=0; j<n; j++)
                    {
                        int sum=0;
                        for(int k =j+1; k<n; k++)
                        {
                            if (arr[j] > arr[k])
                            sum++;
                        }
                        cnt[j] = sum;
                    }
                }
                catch
                {

                }
                if (cnt.Sum() % 2 == 0)
                    Console.WriteLine("YES");
                else
                    Console.WriteLine("NO");
            }
    }
}

Larry’s Array Java Solution

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int c = Integer.parseInt(scan.nextLine());
        for(int i=0;i<c;i++){
            int n = Integer.parseInt(scan.nextLine());
            String[] sp = scan.nextLine().split("\\s+");
            LinkedList<Integer> ll = new LinkedList<Integer>();
            for(int j=0;j<n;j++)ll.add(Integer.parseInt(sp[j]));
            for(int j=0;j<n-2;j++){
                if(ll.get(j)!=j+1){
                    int index = findIndex(ll,j+1);
                    if((index-j)%2==0){
                        int val = ll.remove(index);
                        ll.add(j,val);
                    }
                    else{
                        int val =ll.remove(index);
                        ll.add(j,val);
                        int tmp = ll.remove(j+2);
                        ll.add(j+1,tmp);
                        
                    }
                }
            }
            String res = "YES";
            if(ll.get(n-1) != n)res = "NO";
            System.out.println(res);
        }
    }
    public static int findIndex(LinkedList<Integer> ll, int val){
        for(int i=val;i<ll.size();i++)if(ll.get(i)==val)return i;
            return -1;
    }
}

Larry’s Array JavaScript Solution

function processData(input) {
    input = input.split("\n");
    var cases = Number(input[0]);
    for (var t=0;t<cases;t++) {
        var a = input[t*2+2].split(" ").map(Number);
        for (var i=1;i<=a.length-2;i++) {
            //move i to ith place
            //console.log("moving: "+i);
            //if i is in last place: 
            if (a.indexOf(i)==a.length-1) {
                //console.log("i is in last place, moving it to 2nd to last")
                a[a.length-1] = a[a.length-3];
                a[a.length-3] = a[a.length-2];
                a[a.length-2] = i;
                //console.log(a);
            }
            var moves = a.indexOf(i)+1-i;
            //console.log("moves: "+moves);
            for (var m=0;m<moves;m++) {
                var ri = a.indexOf(i);
                a[ri] = a[ri+1];
                a[ri+1] = a[ri-1];
                a[ri-1] = i;
            }
            //console.log(a);
        }
        if (final3(a)) {
            console.log("YES");
        } else {
            console.log("NO");
        }
    }
} 

function final3(a) {
    return (a[a.length-1]>a[a.length-2]&&a[a.length-2]>a[a.length-3])
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Larry’s Array Python Solution

def rotate(arr, i):
    tmp = arr[i]
    arr[i] = arr[i+1]
    arr[i+1] = arr[i+2]
    arr[i+2] = tmp

def testcase(arr):
    for upto in range(len(arr) - 2, 0, -1):
        for start in range(upto):
            highest = max(arr[start:start+3])
            if arr[start] == highest:
                rotate(arr, start)
            elif arr[start+1] == highest:
                rotate(arr, start)
                rotate(arr, start)
            else:
                pass
    # Now, we need to check the first 3 elements.
    if arr[0] < arr[1] < arr[2]:
        print('YES')
    else:
        print('NO')

testcases = int(input().strip())
for t in range(testcases):
    n = int(input().strip())
    arr = [int(x) for x in input().strip().split()]
    testcase(arr)