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, 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
3 3 3 1 2 4 1 3 4 2 5 1 2 3 5 4
Sample Output
YES YES NO
Larry’s Array HackerRank Solution in C
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
unsigned t;
scanf ("%u", &t);
while (t--) {
unsigned n;
scanf ("%u", &n);
unsigned a[n];
for (unsigned i = 0; i < n; i++) {
scanf ("%u", a + i);
}
unsigned int num_inv = 0;
for (unsigned i = 0; i < n ; i++) {
for (unsigned j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
num_inv++;
}
}
}
if (num_inv % 2) {
printf ("NO\n");
} else {
printf ("YES\n");
}
}
return 0;
}
Larry’s Array HackerRank Solution in 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
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
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;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
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;
reader(&T);
while(T--){
reader(&N);
rep(i,N) reader(A+i);
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;
}
Larry’s Array HackerRank Solution in Java
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int[] aux;
public static long insertSort(int[] ar)
{
aux = new int[ar.length];
long count = mergeSort(ar, 0, ar.length-1);
return count;
}
public static long mergeSort(int[] ar, int from, int to) {
long count = 0;
if (from + 8 >= to) {
for (int i = from+1; i <= to; i++) {
int x = ar[i];
int j = i-1;
while (j >= from && ar[j] > x) {
ar[j+1] = ar[j];
count++;
j--;
}
ar[j+1] = x;
}
return count;
}
int middle = (from + to) / 2;
count += mergeSort(ar, from, middle);
count += mergeSort(ar, middle+1, to);
count += merge(ar, from, middle+1, to);
return count;
}
public static long merge(int[] ar, int from, int second, int to) {
long count = 0;
for (int i = from; i <= to; i++) {
aux[i] = ar[i];
}
int i = from;
int j = second;
int k = from;
while (k <= to) {
if (i >= second) ar[k] = aux[j++];
else if (j > to) ar[k] = aux[i++];
else if (aux[i] <= aux[j]) ar[k] = aux[i++];
else {
ar[k] = aux[j++];
count += (second-i);
}
k++;
}
return count;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int i=0;i<t;i++){
int n = in.nextInt();
int[] ar = new int[n];
for(int j=0;j<n;j++){
ar[j]=in.nextInt();
//System.err.println(ar[j]);
}
long c = insertSort(ar);
String answer = "YES";
if (c%2 == 1) answer = "NO";
System.out.println(answer);
}
}
}
Larry’s Array HackerRank Solution in Python
# Enter your code here. Read input from STDIN. Print output to STDOUT
x=int(raw_input())
for _ in range(x):
raw_input()
arr=[int(i) for i in raw_input().split()]
count=0
for ind,val in enumerate(arr):
count+=sum(i>val for i in arr[:ind])
if count%2==0:
print "YES"
else:
print "NO"
Larry’s Array HackerRank Solution in C#
using System;
using System.Linq;
public class Solution
{
static void Main(String[] args)
{
var t = byte.Parse(Console.ReadLine());
for (int i = 0; i < t; i++)
{
Console.ReadLine();
var inp = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
//var sorted = inp.OrderBy(x => x).ToList();
var sum = 0;
for (int j = 0; j < inp.Count; j++)
{
for (int k = j+1; k < inp.Count; k++)
{
if (inp[k] < inp[j])
sum++;
}
}
Console.WriteLine(sum%2==0?"YES":"NO");
}
}
}
Attempt Larry’s Array HackerRank Challenge
Link – https://www.hackerrank.com/challenges/larrys-array/
Next HackerRank Challenge Solution
Link – https://exploringbits.com/almost-sorted-hackerrank-solution/
