# Hackerrank Larry's Array Solution

Larry has been given a permutation of a sequence of natural numbers incrementing from  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 .

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  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 , the number of test cases.

The next  pairs of lines are as follows:

• The first line contains an integer , the length of .
• The next line contains  space-separated integers .

Constraints.

• integers that increment by  from  to

Output Format.

For each test case, print YES if  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  denotes the number of operations performed.

Test Case 0:

is now sorted, so we print  on a new line.

Test Case 1:
.
.
is now sorted, so we print  on a new line.

Test Case 2:
No sequence of rotations will result in a sorted . Thus, we print  on a new line.

### Solution in java8

Approach 1.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

// Complete the larrysArray function below.
static String larrysArray(int[] A) {
int n=A.length;int k=1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(A[i]>A[j])
k^=1;
else
k^=0;
}
}
if(k==1)
return "YES";
else
return "NO";
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int tItr = 0; tItr < t; tItr++) {
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

int[] A = new int[n];

String[] AItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int i = 0; i < n; i++) {
int AItem = Integer.parseInt(AItems[i]);
A[i] = AItem;
}

String result = larrysArray(A);

bufferedWriter.write(result);
bufferedWriter.newLine();
}

bufferedWriter.close();

scanner.close();
}
}


Approach 2.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

// Complete the larrysArray function below.
static String larrysArray(int[] A) {
int ret = 0;
for(int i = 0; i < A.length; ++i) {
for(int j = i + 1; j < A.length; ++j) {
ret += A[i] > A[j] ? 1 : 0;
ret %= 2;
}
}
return ret == 0 ? "YES" : "NO";

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int tItr = 0; tItr < t; tItr++) {
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

int[] A = new int[n];

String[] AItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int i = 0; i < n; i++) {
int AItem = Integer.parseInt(AItems[i]);
A[i] = AItem;
}

String result = larrysArray(A);

bufferedWriter.write(result);
bufferedWriter.newLine();
}

bufferedWriter.close();

scanner.close();
}
}


Approach 3.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {
public static void rotate(int[] arr, int a){
int temp = arr[a];
arr[a] = arr[a+1];
arr[a+1] = arr[a+2];
arr[a+2] = temp;
}

// Complete the larrysArray function below.
static String larrysArray(int[] ar) {
for(int i = 0; i < ar.length; i++){
for(int j = ar.length-3; j >=i; j--){
while(ar[j] > ar[j+1] || ar[j] > ar[j+2]){
rotate(ar,j);
}
}
}
return ar[ar.length-2] < ar[ar.length-1]? "YES" : "NO";

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int tItr = 0; tItr < t; tItr++) {
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

int[] A = new int[n];

String[] AItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int i = 0; i < n; i++) {
int AItem = Integer.parseInt(AItems[i]);
A[i] = AItem;
}

String result = larrysArray(A);

bufferedWriter.write(result);
bufferedWriter.newLine();
}

bufferedWriter.close();

scanner.close();
}
}


### Solution in python3

Approach 1.

num = int(input())

for _ in range(num):
arr_num = int(input())
arr = map(int, input().strip().split())
print("NO") if sum((1 for i in range(len(arr)) for j in range(i+1, len(arr)) if arr[i] > arr[j] ))%2 else print("YES")


Approach 2.

t=int(input())
for _ in range(t):
count=0
sum1=0
a=int(input())
l=[int(x) for x in input().split()]
for i in range(0,len(l)-1):
count=0
for j in range(i+1,len(l)):
if(l[i]>l[j]):
count=count+1
sum1=sum1+count
if(sum1%2==0):
print("YES")
else:
print("NO")



### Solution in cpp

Approach 1.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {

int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
vector<int>v(n);
for(int j=0;j<n;j++)
cin>>v[j];
int swaps=0;
for(int i=0;i<v.size();i++){
for(int j=0;j<v.size()-1;j++){
if(v[j]>v[j+1]){
swap(v[j],v[j+1]);
swaps++;
}
}
}
if(swaps%2==0)
cout<<"YES"<<endl;
else
cout<<"NO\n";

}
return 0;
}


Approach 2.


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

int main() {
FILE* input = stdin;
int NumTest;
fscanf(input, "%d\n", &NumTest);
for ( int i = 0; i < NumTest; ++i ) {
int Num;
fscanf(input, "%d\n", &Num);
int* data = (int*)(malloc(Num*sizeof(int)));
for ( int d = 0; d < Num; ++d )
fscanf(input, "%d ", data+d);

int CountInversed = 0;
for ( int k = 0; k < Num; ++k )
for ( int j = k+1; j < Num; ++j )
if ( data[k] > data[j] )
++CountInversed;

if ( CountInversed % 2 )
printf("NO\n");
else
printf("YES\n");
free(data);

}
return 0;
}


Approach 3.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
long long int t;
cin >> t;
while(t--)
{
long long int n;
cin >> n;
vector<long long int >v(n);
for(long long int j = 0 ; j < n ; j++)
{
cin >> v[j];
}
long long int NumberOfInversions = 0;
for(long long int i = 0 ; i < n ; i++)
{
for(long long int j = 0 ; j < i ; j++)
{
if(v[j] > v[i])
{
NumberOfInversions++;
}
}
}
if(NumberOfInversions %2 == 0)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}