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