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
TABLE OF CONTENTS
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/
Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.