In this post, we will solve Larry’s Array HackerRank Solution. This problem (Larry’s Array) is a part of HackerRank Problem Solving series.
Task
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]
YESOn 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
NOExplanation
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
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;
}
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.