# Larry’s Array – HackerRank Solution

In this post, we will solve Larry’s Array HackerRank Solution. This problem (Larry’s Array) is a part of HackerRank Problem Solving series.

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  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].

## Constraints

• 1 <= t <= 10
• 3 <= n <= 1000
• 1 <= A[i] <= n
• Asorted = integers that increment by 1 from 1 to n

## Output Format

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

Sample Input

``````3
3
3 1 2
4
1 3 4 2
5
1 2 3 5 4
``````

Sample Output

``````YES
YES
NO``````

Explanation

In the explanation below, the subscript of A denotes the number of operations performed.

Test Case 0:
A0 = {3, 1, 2} -> rotate(3, 1, 2) -> A1 = {1, 2, 3}
A is now sorted, so we print YES on a new line.

Test Case 1:
A0 = {1, 3, 4, 2} -> rotate(3, 4, 2) -> A1 = {1, 4, 2, 3}.
A1 = {1, 4, 2, 3} -> rotate(4, 2, 3) -> A2 = {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.

## Solution – Larry’s Array – HackerRank Solution

### C++

```#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

char memarr[17000000]; void *mem = memarr;
#define MD 1000000007

int T, N, A[1000];

int main(){
int i, j, k;
int res;

while(T--){
res = 0;
rep(i,N) REP(j,i+1,N) if(A[i] > A[j]) res++;
if(res%2) writerLn("NO"); else writerLn("YES");
}

return 0;
}
```

### Python

```import sys

def rotate(A, pos):
A[pos], A[pos+1], A[pos+2] = A[pos+1], A[pos+2], A[pos]

def larrysArray(A):
for _ in range(len(A)):
for ind in range(1, len(A) - 1):
a, b, c = A[ind-1], A[ind], A[ind+1]
#print("ind = {} A = {} B = {} C = {}".format(ind, a, b, c))
if a > b or c < a:
#print("rotating 1")
rotate(A, ind-1)

if A == sorted(A):
return 'YES'
else:
return 'NO'

if __name__ == "__main__":
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
A = list(map(int, input().strip().split(' ')))
result = larrysArray(A)
print(result)
```

### Java

```import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();
for (int tc = 0; tc < T; tc++) {
int N = sc.nextInt();
int[] A = new int[N];
for (int i = 0; i < A.length; i++) {
A[i] = sc.nextInt();
}
System.out.println(solve(A) ? "YES" : "NO");
}

sc.close();
}

static boolean solve(int[] A) {
for (int i = 0; i < A.length; i++) {
int index = find(A, i + 1);

while (index >= i + 2) {
A[index] = A[index - 1];
A[index - 1] = A[index - 2];
A[index - 2] = i + 1;

index -= 2;
}

if (index == i + 1) {
if (index == A.length - 1) {
return false;
}

A[index] = A[index + 1];
A[index + 1] = A[index - 1];
A[index - 1] = i + 1;
}
}
return true;
}

static int find(int[] a, int target) {
for (int i = 0;; i++) {
if (a[i] == target) {
return i;
}
}
}
}
```

Note: This problem (Larry’s Array) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.