HackerRank Larry’s Array Problem Solution
In this post, we will solve HackerRank Larry’s Array Problem Solution.
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 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
NOExplanation
In the explanation below, the subscript of A denotes the number of operations performed.
Test Case 0:
Ao = {3, 1, 2}→ rotate(3, 1, 2)→ A₁ = {1,2,3}
A is now sorted, so we print Yes on a new line.
Test Case 1:
Ao = {1,3,4,2}→ rotate(3, 4, 2)→ A₁ = {1, 4, 2, 3}. A₁ = {1, 4, 2, 3} → rotate(4, 2, 3) → A₂ = {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.
Larry’s Array C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int testcases;
scanf("%d", &testcases);
//printf ("%d", testcases);
int cases = 0;
while (cases < testcases) {
int len;
scanf("%d", &len);
int value[len-1];
int i = 0;
while (i < len){
scanf("%d", &value[i]);
i++;
}
i = 0;
int temp = 0;
while (i < len) {
int j = i+1;
while (j < len) {
if (value[i] > value[j]) {
temp++;
}
j++;
}
i++;
}
if (temp%2 == 0) {
printf("YES\n");
} else {
printf("NO\n");
}
cases++;
}
return 0;
}Larry’s Array C++ Solution
#include <stdio.h>
#include <assert.h>
typedef unsigned int uint_t;
const uint_t T = 10, N = 1000;
static uint_t calc_invs(const uint_t *as, uint_t n) {
uint_t res = 0;
for (uint_t i = 1; i < n; i++) {
for (uint_t j = 0; j < i; j++)
res += (as[j] > as[i]);
}
return res;
}
static uint_t as[N];
int main() {
uint_t t;
int st = scanf("%u", &t);
assert (st == 1);
assert (0 < t && t <= T);
for (uint_t i = 0; i < t; i++) {
uint_t n;
st = scanf("%u", &n);
assert (3 <= n && n <= N);
for (uint_t j = 0; j < n; j++) {
st = scanf("%u", &as[j]);
assert (st == 1);
assert (0 < as[j] && as[j] <= n);
}
uint_t res = calc_invs(as, n) & 1;
printf("%s\n", res ? "NO" : "YES");
}
return 0;
}Larry’s Array C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
int t = Convert.ToInt32(Console.ReadLine());
for(int i=0; i<t; i++)
{
int n = Convert.ToInt32(Console.ReadLine());
string[] temp = Console.ReadLine().Split(' ');
int[] arr = Array.ConvertAll(temp,Int32.Parse);
int[] cnt = new int[n];
try
{
for(int j=0; j<n; j++)
{
int sum=0;
for(int k =j+1; k<n; k++)
{
if (arr[j] > arr[k])
sum++;
}
cnt[j] = sum;
}
}
catch
{
}
if (cnt.Sum() % 2 == 0)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
}Larry’s Array Java Solution
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner scan = new Scanner(System.in);
int c = Integer.parseInt(scan.nextLine());
for(int i=0;i<c;i++){
int n = Integer.parseInt(scan.nextLine());
String[] sp = scan.nextLine().split("\\s+");
LinkedList<Integer> ll = new LinkedList<Integer>();
for(int j=0;j<n;j++)ll.add(Integer.parseInt(sp[j]));
for(int j=0;j<n-2;j++){
if(ll.get(j)!=j+1){
int index = findIndex(ll,j+1);
if((index-j)%2==0){
int val = ll.remove(index);
ll.add(j,val);
}
else{
int val =ll.remove(index);
ll.add(j,val);
int tmp = ll.remove(j+2);
ll.add(j+1,tmp);
}
}
}
String res = "YES";
if(ll.get(n-1) != n)res = "NO";
System.out.println(res);
}
}
public static int findIndex(LinkedList<Integer> ll, int val){
for(int i=val;i<ll.size();i++)if(ll.get(i)==val)return i;
return -1;
}
}Larry’s Array JavaScript Solution
function processData(input) {
input = input.split("\n");
var cases = Number(input[0]);
for (var t=0;t<cases;t++) {
var a = input[t*2+2].split(" ").map(Number);
for (var i=1;i<=a.length-2;i++) {
//move i to ith place
//console.log("moving: "+i);
//if i is in last place:
if (a.indexOf(i)==a.length-1) {
//console.log("i is in last place, moving it to 2nd to last")
a[a.length-1] = a[a.length-3];
a[a.length-3] = a[a.length-2];
a[a.length-2] = i;
//console.log(a);
}
var moves = a.indexOf(i)+1-i;
//console.log("moves: "+moves);
for (var m=0;m<moves;m++) {
var ri = a.indexOf(i);
a[ri] = a[ri+1];
a[ri+1] = a[ri-1];
a[ri-1] = i;
}
//console.log(a);
}
if (final3(a)) {
console.log("YES");
} else {
console.log("NO");
}
}
}
function final3(a) {
return (a[a.length-1]>a[a.length-2]&&a[a.length-2]>a[a.length-3])
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Larry’s Array Python Solution
def rotate(arr, i):
tmp = arr[i]
arr[i] = arr[i+1]
arr[i+1] = arr[i+2]
arr[i+2] = tmp
def testcase(arr):
for upto in range(len(arr) - 2, 0, -1):
for start in range(upto):
highest = max(arr[start:start+3])
if arr[start] == highest:
rotate(arr, start)
elif arr[start+1] == highest:
rotate(arr, start)
rotate(arr, start)
else:
pass
# Now, we need to check the first 3 elements.
if arr[0] < arr[1] < arr[2]:
print('YES')
else:
print('NO')
testcases = int(input().strip())
for t in range(testcases):
n = int(input().strip())
arr = [int(x) for x in input().strip().split()]
testcase(arr)Other Solutions
