In this HackerRank Almost Sorted problem, you have Given an array of integers, determine whether the array can be sorted in ascending order using either swap two elements or reverse one sub-segment.
Problem solution in Python programming.
def getJumps(ar):
jumps = []
for i in range(len(ar)-1):
if ar[i] > ar[i+1]:
jumps.append(i)
return jumps
def isSortedWithSwap(ar, i, j):
ar[i], ar[j] = ar[j], ar[i]
jumps = getJumps(ar)
ar[i], ar[j] = ar[j], ar[i] # repair list
return len(jumps) == 0
def isSortedWithReverse(ar, i, j):
ar[i:j] = ar[j-1:i+1:-1]
jumps = getJumps(ar)
ar[i:j] = ar[j-1:i+1:-1] # repair list
return len(jumps) == 0
def magic(ar):
jumps = getJumps(ar)
if len(jumps) == 0:
print('yes')
elif len(jumps) == 1:
i = jumps[0]
j = i+1
while j+1 < len(ar) and ar[i+1] == ar[j+1]: #move point to last same element
j+=1
if isSortedWithSwap(ar, i, j):
print('yes')
print('swap', i+1, j+1)
else:
print('no')
elif len(jumps) == 2:
i = jumps[0]
j = jumps[1] + 1
if isSortedWithSwap(ar, i, j):
print('yes')
print('swap', i+1, j+1)
else:
print('no')
else:
i = jumps[0]
j = jumps[-1] + 2
if isSortedWithReverse(ar,i,j):
print('yes')
print('reverse', i+1, j)
else:
print('no')
n = int(input())
ar = list(map(int, input().split()))
magic(ar)Problem solution in Java Programming.
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 sc = new Scanner(System.in);
int start = -1;int count = 0;int end = -1;
int prev_i = -1;
int size = sc.nextInt();
int arr[] = new int [size];
int i;
for(int j = 0;j<size;j++){
arr[j] = sc.nextInt();
}
if(findSwap(arr)==-1){
findReverse(arr);
}
}
static int findReverse(int [] arr){
int start =-1;int end = -1;
for(int i = 0;i<arr.length-1;i++){
if(arr[i]>arr[i+1]){
if(start==-1){
start = i;
}
else{
System.out.println("no");
return -1;
}
while(arr[i]>arr[i+1]){
end = i+1;
i++;
}
if((start==0||arr[start-1]<arr[end])&&(end==arr.length-1||arr[start]<arr[end+1])){
continue;
}
else{
System.out.println("no");
return -1;
}
}
}
System.out.println("yes");
System.out.println("reverse "+(start+1)+" "+(end+1));
return 1;
}
static int findSwap(int [] arr){
int count =0;int start = -1;int end =-1;
for(int i = 0;i<arr.length-1;i++){
if(arr[i]>arr[i+1]){
count++;
if(count==1){
start = i;
end = i+1;
}
else{
if(count==2){
end=i+1;
}else{
return -1;
}
}
}
}
if((end!=arr.length-1)&&(arr[start]<arr[end+1]))
{
System.out.println("yes");
System.out.println("swap "+(start+1)+" "+(end+1));
return 1;
}
else{
if((end==arr.length-1)&&(start==(end-1))){
System.out.println("yes");
System.out.println("swap "+(start+1)+" "+(end+1));
return 1;
}
}
return -1;
}
}
Problem solution in C++ programming.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> A(n);
for (int i = 0; i < n; i++) {
cin >> A[i];
}
vector<int> B(A);
sort(B.begin(), B.end());
int start = -1, end = -1;
int count = 0;
for (int i = 0; i < n; i++) {
if (A[i] != B[i]) {
count++;
if (start == -1) {
start = i;
}
end = i;
}
}
if (count == 2) {
cout << "yes"<<endl;
cout << "swap ";
cout << start + 1<<" "<<end + 1<<endl;
return 0;
}
for (int i = 0; i < count / 2; i++) {
if (A[end - i] != B[start + i]) {
cout << "no" <<endl;
return 0;
}
}
cout << "yes"<<endl;
cout << "reverse "<<start + 1<<" "<<end + 1<<endl;
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
Problem solution in C programming.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int *a, ar;
int pos1 = -1, pos2 = -1, reverse = 0, swap = 0;
int reverse_possible = 1;
// get size of array and add elements to array
scanf("%d", &ar);
a = (int*)malloc(sizeof(int) * ar);
for (int i = 0; i < ar; i++) {
scanf("%d", a + i);
}
// work goes here
for (int i = 0; i < ar; i++) {
// we note that all numbers in the array are distinct
if (i < ar - 1) {
if (a[i] > a[i + 1]) {
if (swap || reverse) {
swap = reverse = 0;
break;
}
if (pos1 == -1) {
pos1 = i;
pos2 = i;
} else if (reverse_possible && !reverse) {
pos2++;
}
} else if (pos2 != -1 && !swap && !reverse) {
// potentially a reverse operation
if (pos2 - pos1 >= 2) {
reverse = 1;
continue;
// continue finding reverse
} else {
pos2 = -1;
reverse_possible = 0;
}
}
}
// note that a[pos1] >= a[i]
if (pos1 != -1 && a[pos1] > a[i] &&
((i+1<ar && a[pos1] <= a[i+1]) || i+1>=ar) &&
((i-1>=0 && a[i-1] <= a[pos1]) || i-1<0) &&
((pos1+1<ar && a[i] <= a[pos1+1]) || pos1+1>=ar) &&
((pos1-1>=0 && a[pos1-1] <= a[i]) || pos1-1<0)) {
if (swap || reverse) {
swap = 0;
reverse = 0;
break;
}
pos2 = i;
swap = 1;
}
}
//printf("%d %d\n", swap, reverse);
if (reverse) {
printf("yes\n");
printf("reverse %d %d", pos1 + 1, pos2 + 2);
} else if (swap) {
printf("yes\n");
printf("swap %d %d", pos1 + 1, pos2 + 1);
} else {
printf("no\n");
}
return 0;
}
Problem solution in JavaScript programming.
function processData(input) {
var lines = input.split("\n");
lines.shift();
var array = lines[0].split(" ").map(function (v) {
return parseInt(v);
});
solve(array);
}
function countDownMarks(array) {
var downMarks = [];
for (var i = 0; i < array.length - 1; i++) {
if (array[i + 1] < array[i]) {
downMarks.push(i);
}
}
return downMarks;
}
function solve(array) {
var downMarks = countDownMarks(array);
var newArray, newDownMarks, start, end;
// try swap
if (downMarks.length == 1 ||
downMarks.length == 2) {
newArray = array.slice(0);
start = downMarks.shift();
end = (downMarks.length) ? downMarks.shift() + 1 : start + 1;
swap(newArray, start, end);
newDownMarks = countDownMarks(newArray);
if (!newDownMarks.length) {
outputResult("yes");
output("swap", start + 1, end + 1);
return;
}
}
// try reverse
if (downMarks.length > 2 &&
downMarks.length == downMarks[downMarks.length - 1] - downMarks[0] + 1) {
start = downMarks.shift();
end = downMarks.pop() + 1;
newArray = reverse(array, start, end);
newDownMarks = countDownMarks(newArray);
if (!newDownMarks.length) {
outputResult("yes");
output("reverse", start + 1, end + 1);
return;
}
}
outputResult("no");
}
function swap(array, idx1, idx2) {
var tmp = array[idx1];
array[idx1] = array[idx2];
array[idx2] = tmp;
}
function reverse(array, idx1, idx2) {
return array.slice(0, idx1).concat(array.slice(idx1, idx2 + 1).reverse()).concat(array.slice(idx2 + 1));
}
function output(op, start, end) {
process.stdout.write([op, start, end].join(" "));
}
function outputResult(str) {
process.stdout.write(str+"\n");
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
0 Comments