Hackerrank Larry's Array Solution
5 min read

Hackerrank Larry's Array Solution

Hackerrank Larry's Array Solution

Larry has been given a permutation of a sequence of natural numbers incrementing from  as an array.  He must determine whether the array can be sorted using the following operation any number of times:

  • Choose any  consecutive indices and rotate their elements in such a way that .

For example, if :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  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 , the number of test cases.

The next  pairs of lines are as follows:

  • The first line contains an integer , the length of .
  • The next line contains  space-separated integers .

Constraints.

  • integers that increment by  from  to

Output Format.

For each test case, print YES if  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

Explanation.

In the explanation below, the subscript of  denotes the number of operations performed.

Test Case 0:

is now sorted, so we print  on a new line.

Test Case 1:
.
.
is now sorted, so we print  on a new line.

Test Case 2:
No sequence of rotations will result in a sorted . Thus, we print  on a new line.

Solution in java8

Approach 1.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the larrysArray function below.
    static String larrysArray(int[] A) {
int n=A.length;int k=1;
for(int i=0;i<n;i++)
{
    for(int j=i+1;j<n;j++)
    {   
        if(A[i]>A[j])
        k^=1;
        else
        k^=0;
    }
}
if(k==1)
return "YES";
else
return "NO";
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] A = new int[n];

            String[] AItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int AItem = Integer.parseInt(AItems[i]);
                A[i] = AItem;
            }

            String result = larrysArray(A);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Approach 2.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the larrysArray function below.
    static String larrysArray(int[] A) {
        int ret = 0;
        for(int i = 0; i < A.length; ++i) {
            for(int j = i + 1; j < A.length; ++j) {
                ret += A[i] > A[j] ? 1 : 0;
                ret %= 2;
            }
        }
        return ret == 0 ? "YES" : "NO";

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] A = new int[n];

            String[] AItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int AItem = Integer.parseInt(AItems[i]);
                A[i] = AItem;
            }

            String result = larrysArray(A);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Approach 3.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {
    public static void rotate(int[] arr, int a){
            int temp = arr[a];
            arr[a] = arr[a+1];
            arr[a+1] = arr[a+2];
            arr[a+2] = temp;
        }

    // Complete the larrysArray function below.
    static String larrysArray(int[] ar) {
        for(int i = 0; i < ar.length; i++){
            for(int j = ar.length-3; j >=i; j--){
                while(ar[j] > ar[j+1] || ar[j] > ar[j+2]){
                    rotate(ar,j);
                }
            }
        }
        return ar[ar.length-2] < ar[ar.length-1]? "YES" : "NO";

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] A = new int[n];

            String[] AItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int AItem = Integer.parseInt(AItems[i]);
                A[i] = AItem;
            }

            String result = larrysArray(A);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Solution in python3

Approach 1.

num = int(input())

for _ in range(num):
    arr_num = int(input())
    arr = map(int, input().strip().split())
    print("NO") if sum((1 for i in range(len(arr)) for j in range(i+1, len(arr)) if arr[i] > arr[j] ))%2 else print("YES")

Approach 2.

t=int(input())
for _ in range(t):
    count=0
    sum1=0
    a=int(input())
    l=[int(x) for x in input().split()]
    for i in range(0,len(l)-1):
        count=0
        for j in range(i+1,len(l)):
            if(l[i]>l[j]):
                count=count+1
        sum1=sum1+count
    if(sum1%2==0):
        print("YES")
    else:
        print("NO")
        
        
        

Solution in cpp

Approach 1.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int n;
        cin>>n;
        vector<int>v(n);
        for(int j=0;j<n;j++)
            cin>>v[j];
        int swaps=0;
        for(int i=0;i<v.size();i++){
            for(int j=0;j<v.size()-1;j++){
                if(v[j]>v[j+1]){
                    swap(v[j],v[j+1]);
                    swaps++;
                }
            }
        }
        if(swaps%2==0)
            cout<<"YES"<<endl;
        else
            cout<<"NO\n";
        
    }
    return 0;
}

Approach 2.


#include <stdio.h>
#include <stdlib.h>

int main() {
    FILE* input = stdin;
    int NumTest;
    fscanf(input, "%d\n", &NumTest);
    for ( int i = 0; i < NumTest; ++i ) {
        int Num;
        fscanf(input, "%d\n", &Num);
        int* data = (int*)(malloc(Num*sizeof(int)));
        for ( int d = 0; d < Num; ++d )
            fscanf(input, "%d ", data+d);
        
        int CountInversed = 0;
        for ( int k = 0; k < Num; ++k )
            for ( int j = k+1; j < Num; ++j )
                if ( data[k] > data[j] )
                    ++CountInversed;
      
        if ( CountInversed % 2 ) 
            printf("NO\n");
        else
            printf("YES\n");
        free(data);
        
    }
    return 0;
}

Approach 3.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    long long int t;
    cin >> t;
    while(t--)
    {
        long long int n;
        cin >> n;
        vector<long long int >v(n);
        for(long long int j = 0 ; j < n ; j++)
        {
            cin >> v[j];
        }
        long long int NumberOfInversions = 0;
        for(long long int i = 0 ; i < n ; i++)
        {
            for(long long int j = 0 ; j < i ; j++)
            {
                if(v[j] > v[i])
                {
                    NumberOfInversions++;
                }
            }
        }
        if(NumberOfInversions %2 == 0)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×