Larry’s Array HackerRank Solution in C, C++, Java, Python

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() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    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/

Leave a Comment