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;
}